~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: 2009-04-09 20:23:07 UTC
  • mfrom: (4265.1.4 bbc-merge)
  • Revision ID: pqm@pqm.ubuntu.com-20090409202307-n0depb16qepoe21o
(jam) Change _fetch_uses_deltas = False for CHK repos until we can
        write a better fix.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006, 2007 Canonical Ltd
 
1
# Copyright (C) 2006, 2007, 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""DirState objects record the state of a directory and its bzr metadata.
18
18
 
29
29
 
30
30
dirstate format = header line, full checksum, row count, parent details,
31
31
 ghost_details, entries;
32
 
header line = "#bazaar dirstate flat format 2", NL;
 
32
header line = "#bazaar dirstate flat format 3", NL;
33
33
full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
34
 
row count = "num_entries: ", digit, NL;
 
34
row count = "num_entries: ", WHOLE_NUMBER, NL;
35
35
parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
36
36
ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
37
37
entries = {entry};
82
82
'a' is an absent entry: In that tree the id is not present at this path.
83
83
'd' is a directory entry: This path in this tree is a directory with the
84
84
    current file id. There is no fingerprint for directories.
85
 
'f' is a file entry: As for directory, but its a file. The fingerprint is a
86
 
    sha1 value.
 
85
'f' is a file entry: As for directory, but it's a file. The fingerprint is the
 
86
    sha1 value of the file's canonical form, i.e. after any read filters have
 
87
    been applied to the convenience form stored in the working tree.
87
88
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
88
89
    link target.
89
90
't' is a reference to a nested subtree; the fingerprint is the referenced
99
100
 
100
101
--- Format 1 had the following different definition: ---
101
102
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
102
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target, 
 
103
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
103
104
    {PARENT ROW}
104
105
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
105
106
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
118
119
where we need id->path mapping; we also usually read the whole file, so
119
120
I'm going to skip that for the moment, as we have the ability to locate
120
121
via bisect any path in any tree, and if we lookup things by path, we can
121
 
accumulate a id->path mapping as we go, which will tend to match what we
 
122
accumulate an id->path mapping as we go, which will tend to match what we
122
123
looked for.
123
124
 
124
125
I plan to implement this asap, so please speak up now to alter/tweak the
130
131
operations for the less common but still occurs a lot status/diff/commit
131
132
on specific files). Operations on specific files involve a scan for all
132
133
the children of a path, *in every involved tree*, which the current
133
 
format did not accommodate. 
 
134
format did not accommodate.
134
135
----
135
136
 
136
137
Design priorities:
143
144
Locking:
144
145
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
145
146
 been modified, but will require that we flush/ignore cached stat-hit data
146
 
 because we wont want to restat all files on disk just because a lock was
 
147
 because we won't want to restat all files on disk just because a lock was
147
148
 acquired, yet we cannot trust the data after the previous lock was released.
148
149
 
149
150
Memory representation:
150
151
 vector of all directories, and vector of the childen ?
151
 
   i.e. 
152
 
     root_entrie = (direntry for root, [parent_direntries_for_root]), 
 
152
   i.e.
 
153
     root_entrie = (direntry for root, [parent_direntries_for_root]),
153
154
     dirblocks = [
154
155
     ('', ['data for achild', 'data for bchild', 'data for cchild'])
155
156
     ('dir', ['achild', 'cchild', 'echild'])
158
159
    - in-order for serialisation - this is 'dirblock' grouping.
159
160
    - insertion of a file '/a' affects only the '/' child-vector, that is, to
160
161
      insert 10K elements from scratch does not generates O(N^2) memoves of a
161
 
      single vector, rather each individual, which tends to be limited to a 
162
 
      manageable number. Will scale badly on trees with 10K entries in a 
 
162
      single vector, rather each individual, which tends to be limited to a
 
163
      manageable number. Will scale badly on trees with 10K entries in a
163
164
      single directory. compare with Inventory.InventoryDirectory which has
164
165
      a dictionary for the children. No bisect capability, can only probe for
165
 
      exact matches, or grab all elements and sorta.
166
 
    - Whats the risk of error here? Once we have the base format being processed
167
 
      we should have a net win regardless of optimality. So we are going to 
168
 
      go with what seems reasonably.
 
166
      exact matches, or grab all elements and sort.
 
167
    - What's the risk of error here? Once we have the base format being processed
 
168
      we should have a net win regardless of optimality. So we are going to
 
169
      go with what seems reasonable.
169
170
open questions:
170
171
 
171
 
maybe we should do a test profile of these core structure - 10K simulated searches/lookups/etc?
 
172
Maybe we should do a test profile of the core structure - 10K simulated
 
173
searches/lookups/etc?
172
174
 
173
175
Objects for each row?
174
176
The lifetime of Dirstate objects is current per lock, but see above for
185
187
the file on disk, and then immediately discard, the overhead of object creation
186
188
becomes a significant cost.
187
189
 
188
 
Figures: Creating a tuple from from 3 elements was profiled at 0.0625
 
190
Figures: Creating a tuple from 3 elements was profiled at 0.0625
189
191
microseconds, whereas creating a object which is subclassed from tuple was
190
192
0.500 microseconds, and creating an object with 3 elements and slots was 3
191
193
microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get
199
201
 
200
202
"""
201
203
 
202
 
 
203
 
import base64
204
204
import bisect
 
205
import binascii
205
206
import errno
206
207
import os
207
208
from stat import S_IEXEC
 
209
import stat
208
210
import struct
209
211
import sys
210
212
import time
211
213
import zlib
212
214
 
213
215
from bzrlib import (
 
216
    cache_utf8,
 
217
    debug,
214
218
    errors,
215
219
    inventory,
216
220
    lock,
219
223
    )
220
224
 
221
225
 
222
 
class _Bisector(object):
223
 
    """This just keeps track of information as we are bisecting."""
 
226
# This is the Windows equivalent of ENOTDIR
 
227
# It is defined in pywin32.winerror, but we don't want a strong dependency for
 
228
# just an error code.
 
229
ERROR_PATH_NOT_FOUND = 3
 
230
ERROR_DIRECTORY = 267
 
231
 
 
232
 
 
233
if not getattr(struct, '_compile', None):
 
234
    # Cannot pre-compile the dirstate pack_stat
 
235
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
 
236
        """Convert stat values into a packed representation."""
 
237
        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),
 
238
            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,
 
239
            st.st_mode))[:-1]
 
240
else:
 
241
    # compile the struct compiler we need, so as to only do it once
 
242
    from _struct import Struct
 
243
    _compiled_pack = Struct('>LLLLLL').pack
 
244
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):
 
245
        """Convert stat values into a packed representation."""
 
246
        # jam 20060614 it isn't really worth removing more entries if we
 
247
        # are going to leave it in packed form.
 
248
        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
 
249
        # With all entries, filesize is 5.9M and read time is maybe 280ms
 
250
        # well within the noise margin
 
251
 
 
252
        # base64 encoding always adds a final newline, so strip it off
 
253
        # The current version
 
254
        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),
 
255
            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
256
        # This is 0.060s / 1.520s faster by not encoding as much information
 
257
        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
 
258
        # This is not strictly faster than _encode(_pack())[:-1]
 
259
        # return '%X.%X.%X.%X.%X.%X' % (
 
260
        #      st.st_size, int(st.st_mtime), int(st.st_ctime),
 
261
        #      st.st_dev, st.st_ino, st.st_mode)
 
262
        # Similar to the _encode(_pack('>LL'))
 
263
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
 
264
 
 
265
 
 
266
class SHA1Provider(object):
 
267
    """An interface for getting sha1s of a file."""
 
268
 
 
269
    def sha1(self, abspath):
 
270
        """Return the sha1 of a file given its absolute path.
 
271
 
 
272
        :param abspath:  May be a filesystem encoded absolute path
 
273
             or a unicode path.
 
274
        """
 
275
        raise NotImplementedError(self.sha1)
 
276
 
 
277
    def stat_and_sha1(self, abspath):
 
278
        """Return the stat and sha1 of a file given its absolute path.
 
279
        
 
280
        :param abspath:  May be a filesystem encoded absolute path
 
281
             or a unicode path.
 
282
 
 
283
        Note: the stat should be the stat of the physical file
 
284
        while the sha may be the sha of its canonical content.
 
285
        """
 
286
        raise NotImplementedError(self.stat_and_sha1)
 
287
 
 
288
 
 
289
class DefaultSHA1Provider(SHA1Provider):
 
290
    """A SHA1Provider that reads directly from the filesystem."""
 
291
 
 
292
    def sha1(self, abspath):
 
293
        """Return the sha1 of a file given its absolute path."""
 
294
        return osutils.sha_file_by_name(abspath)
 
295
 
 
296
    def stat_and_sha1(self, abspath):
 
297
        """Return the stat and sha1 of a file given its absolute path."""
 
298
        file_obj = file(abspath, 'rb')
 
299
        try:
 
300
            statvalue = os.fstat(file_obj.fileno())
 
301
            sha1 = osutils.sha_file(file_obj)
 
302
        finally:
 
303
            file_obj.close()
 
304
        return statvalue, sha1
224
305
 
225
306
 
226
307
class DirState(object):
228
309
 
229
310
    A dirstate is a specialised data structure for managing local working
230
311
    tree state information. Its not yet well defined whether it is platform
231
 
    specific, and if it is how we detect/parameterise that.
 
312
    specific, and if it is how we detect/parameterize that.
232
313
 
233
314
    Dirstates use the usual lock_write, lock_read and unlock mechanisms.
234
315
    Unlike most bzr disk formats, DirStates must be locked for reading, using
255
336
            'r': 'relocated',
256
337
            't': 'tree-reference',
257
338
        }
 
339
    _stat_to_minikind = {
 
340
        stat.S_IFDIR:'d',
 
341
        stat.S_IFREG:'f',
 
342
        stat.S_IFLNK:'l',
 
343
    }
258
344
    _to_yesno = {True:'y', False: 'n'} # TODO profile the performance gain
259
345
     # of using int conversion rather than a dict here. AND BLAME ANDREW IF
260
346
     # it is faster.
276
362
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
277
363
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
278
364
 
279
 
    def __init__(self, path):
 
365
    def __init__(self, path, sha1_provider):
280
366
        """Create a  DirState object.
281
367
 
282
 
        Attributes of note:
283
 
 
284
 
        :attr _root_entrie: The root row of the directory/file information,
285
 
            - contains the path to / - '', ''
286
 
            - kind of 'directory',
287
 
            - the file id of the root in utf8
288
 
            - size of 0
289
 
            - a packed state
290
 
            - and no sha information.
291
368
        :param path: The path at which the dirstate file on disk should live.
 
369
        :param sha1_provider: an object meeting the SHA1Provider interface.
292
370
        """
293
371
        # _header_state and _dirblock_state represent the current state
294
372
        # of the dirstate metadata and the per-row data respectiely.
296
374
        # IN_MEMORY_UNMODIFIED indicates that what we have in memory
297
375
        #   is the same as is on disk
298
376
        # IN_MEMORY_MODIFIED indicates that we have a modified version
299
 
        #   of what is on disk. 
 
377
        #   of what is on disk.
300
378
        # In future we will add more granularity, for instance _dirblock_state
301
379
        # will probably support partially-in-memory as a separate variable,
302
380
        # allowing for partially-in-memory unmodified and partially-in-memory
303
381
        # modified states.
304
382
        self._header_state = DirState.NOT_IN_MEMORY
305
383
        self._dirblock_state = DirState.NOT_IN_MEMORY
 
384
        # If true, an error has been detected while updating the dirstate, and
 
385
        # for safety we're not going to commit to disk.
 
386
        self._changes_aborted = False
306
387
        self._dirblocks = []
307
388
        self._ghosts = []
308
389
        self._parents = []
311
392
        self._lock_token = None
312
393
        self._lock_state = None
313
394
        self._id_index = None
 
395
        # a map from packed_stat to sha's.
 
396
        self._packed_stat_index = None
314
397
        self._end_of_header = None
315
398
        self._cutoff_time = None
316
399
        self._split_path_cache = {}
317
400
        self._bisect_page_size = DirState.BISECT_PAGE_SIZE
 
401
        self._sha1_provider = sha1_provider
 
402
        if 'hashcache' in debug.debug_flags:
 
403
            self._sha1_file = self._sha1_file_and_mutter
 
404
        else:
 
405
            self._sha1_file = self._sha1_provider.sha1
 
406
        # These two attributes provide a simple cache for lookups into the
 
407
        # dirstate in-memory vectors. By probing respectively for the last
 
408
        # block, and for the next entry, we save nearly 2 bisections per path
 
409
        # during commit.
 
410
        self._last_block_index = None
 
411
        self._last_entry_index = None
318
412
 
319
413
    def __repr__(self):
320
414
        return "%s(%r)" % \
324
418
        """Add a path to be tracked.
325
419
 
326
420
        :param path: The path within the dirstate - '' is the root, 'foo' is the
327
 
            path foo within the root, 'foo/bar' is the path bar within foo 
 
421
            path foo within the root, 'foo/bar' is the path bar within foo
328
422
            within the root.
329
423
        :param file_id: The file id of the path being added.
330
 
        :param kind: The kind of the path, as a string like 'file', 
 
424
        :param kind: The kind of the path, as a string like 'file',
331
425
            'directory', etc.
332
426
        :param stat: The output of os.lstat for the path.
333
 
        :param fingerprint: The sha value of the file,
 
427
        :param fingerprint: The sha value of the file's canonical form (i.e.
 
428
            after any read filters have been applied),
334
429
            or the target of a symlink,
335
430
            or the referenced revision id for tree-references,
336
431
            or '' for directories.
337
432
        """
338
433
        # adding a file:
339
 
        # find the block its in. 
 
434
        # find the block its in.
340
435
        # find the location in the block.
341
436
        # check its not there
342
437
        # add it.
343
 
        #------- copied from inventory.make_entry
 
438
        #------- copied from inventory.ensure_normalized_name - keep synced.
344
439
        # --- normalized_filename wants a unicode basename only, so get one.
345
440
        dirname, basename = osutils.split(path)
346
441
        # we dont import normalized_filename directly because we want to be
355
450
        # in the parent, or according to the special treatment for the root
356
451
        if basename == '.' or basename == '..':
357
452
            raise errors.InvalidEntryName(path)
358
 
        # now that we've normalised, we need the correct utf8 path and 
 
453
        # now that we've normalised, we need the correct utf8 path and
359
454
        # dirname and basename elements. This single encode and split should be
360
455
        # faster than three separate encodes.
361
456
        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
362
457
        dirname, basename = osutils.split(utf8path)
363
 
        assert file_id.__class__ == str, \
364
 
            "must be a utf8 file_id not %s" % (type(file_id))
 
458
        # uses __class__ for speed; the check is needed for safety
 
459
        if file_id.__class__ is not str:
 
460
            raise AssertionError(
 
461
                "must be a utf8 file_id not %s" % (type(file_id), ))
365
462
        # Make sure the file_id does not exist in this tree
366
 
        file_id_entry = self._get_entry(0, fileid_utf8=file_id)
 
463
        rename_from = None
 
464
        file_id_entry = self._get_entry(0, fileid_utf8=file_id, include_deleted=True)
367
465
        if file_id_entry != (None, None):
368
 
            path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
369
 
            kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
370
 
            info = '%s:%s' % (kind, path)
371
 
            raise errors.DuplicateFileId(file_id, info)
 
466
            if file_id_entry[1][0][0] == 'a':
 
467
                if file_id_entry[0] != (dirname, basename, file_id):
 
468
                    # set the old name's current operation to rename
 
469
                    self.update_minimal(file_id_entry[0],
 
470
                        'r',
 
471
                        path_utf8='',
 
472
                        packed_stat='',
 
473
                        fingerprint=utf8path
 
474
                    )
 
475
                    rename_from = file_id_entry[0][0:2]
 
476
            else:
 
477
                path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
 
478
                kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
 
479
                info = '%s:%s' % (kind, path)
 
480
                raise errors.DuplicateFileId(file_id, info)
372
481
        first_key = (dirname, basename, '')
373
482
        block_index, present = self._find_block_index_from_key(first_key)
374
483
        if present:
375
484
            # check the path is not in the tree
376
485
            block = self._dirblocks[block_index][1]
377
486
            entry_index, _ = self._find_entry_index(first_key, block)
378
 
            while (entry_index < len(block) and 
 
487
            while (entry_index < len(block) and
379
488
                block[entry_index][0][0:2] == first_key[0:2]):
380
489
                if block[entry_index][1][0][0] not in 'ar':
381
490
                    # this path is in the dirstate in the current tree.
401
510
            packed_stat = pack_stat(stat)
402
511
        parent_info = self._empty_parent_info()
403
512
        minikind = DirState._kind_to_minikind[kind]
 
513
        if rename_from is not None:
 
514
            if rename_from[0]:
 
515
                old_path_utf8 = '%s/%s' % rename_from
 
516
            else:
 
517
                old_path_utf8 = rename_from[1]
 
518
            parent_info[0] = ('r', old_path_utf8, 0, False, '')
404
519
        if kind == 'file':
405
520
            entry_data = entry_key, [
406
521
                (minikind, fingerprint, size, False, packed_stat),
423
538
        if not present:
424
539
            block.insert(entry_index, entry_data)
425
540
        else:
426
 
            assert block[entry_index][1][0][0] == 'a', " %r(%r) already added" % (basename, file_id)
 
541
            if block[entry_index][1][0][0] != 'a':
 
542
                raise AssertionError(" %r(%r) already added" % (basename, file_id))
427
543
            block[entry_index][1][0] = entry_data[1][0]
428
544
 
429
545
        if kind == 'directory':
433
549
        if self._id_index:
434
550
            self._id_index.setdefault(entry_key[2], set()).add(entry_key)
435
551
 
436
 
    def _bisect(self, dir_name_list):
 
552
    def _bisect(self, paths):
437
553
        """Bisect through the disk structure for specific rows.
438
554
 
439
 
        :param dir_name_list: A list of (dir, name) pairs.
440
 
        :return: A dict mapping (dir, name) => entry for found entries. Missing
 
555
        :param paths: A list of paths to find
 
556
        :return: A dict mapping path => entries for found entries. Missing
441
557
                 entries will not be in the map.
 
558
                 The list is not sorted, and entries will be populated
 
559
                 based on when they were read.
442
560
        """
443
561
        self._requires_lock()
444
562
        # We need the file pointer to be right after the initial header block
446
564
        # If _dirblock_state was in memory, we should just return info from
447
565
        # there, this function is only meant to handle when we want to read
448
566
        # part of the disk.
449
 
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
 
567
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
 
568
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
450
569
 
451
570
        # The disk representation is generally info + '\0\n\0' at the end. But
452
571
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
464
583
        found = {}
465
584
 
466
585
        # Avoid infinite seeking
467
 
        max_count = 30*len(dir_name_list)
 
586
        max_count = 30*len(paths)
468
587
        count = 0
469
588
        # pending is a list of places to look.
470
589
        # each entry is a tuple of low, high, dir_names
472
591
        #   high -> the last byte offset (inclusive)
473
592
        #   dir_names -> The list of (dir, name) pairs that should be found in
474
593
        #                the [low, high] range
475
 
        pending = [(low, high, dir_name_list)]
 
594
        pending = [(low, high, paths)]
476
595
 
477
596
        page_size = self._bisect_page_size
478
597
 
531
650
                # Find what entries we are looking for, which occur before and
532
651
                # after this first record.
533
652
                after = start
534
 
                first_dir_name = (first_fields[1], first_fields[2])
535
 
                first_loc = bisect.bisect_left(cur_files, first_dir_name)
 
653
                if first_fields[1]:
 
654
                    first_path = first_fields[1] + '/' + first_fields[2]
 
655
                else:
 
656
                    first_path = first_fields[2]
 
657
                first_loc = _bisect_path_left(cur_files, first_path)
536
658
 
537
659
                # These exist before the current location
538
660
                pre = cur_files[:first_loc]
555
677
                else:
556
678
                    after = mid + len(block)
557
679
 
558
 
                last_dir_name = (last_fields[1], last_fields[2])
559
 
                last_loc = bisect.bisect_right(post, last_dir_name)
 
680
                if last_fields[1]:
 
681
                    last_path = last_fields[1] + '/' + last_fields[2]
 
682
                else:
 
683
                    last_path = last_fields[2]
 
684
                last_loc = _bisect_path_right(post, last_path)
560
685
 
561
686
                middle_files = post[:last_loc]
562
687
                post = post[last_loc:]
567
692
                    # Either we will find them here, or we can mark them as
568
693
                    # missing.
569
694
 
570
 
                    if middle_files[0] == first_dir_name:
 
695
                    if middle_files[0] == first_path:
571
696
                        # We might need to go before this location
572
 
                        pre.append(first_dir_name)
573
 
                    if middle_files[-1] == last_dir_name:
574
 
                        post.insert(0, last_dir_name)
 
697
                        pre.append(first_path)
 
698
                    if middle_files[-1] == last_path:
 
699
                        post.insert(0, last_path)
575
700
 
576
701
                    # Find out what paths we have
577
 
                    paths = {first_dir_name:[first_fields]}
578
 
                    # last_dir_name might == first_dir_name so we need to be
 
702
                    paths = {first_path:[first_fields]}
 
703
                    # last_path might == first_path so we need to be
579
704
                    # careful if we should append rather than overwrite
580
705
                    if last_entry_num != first_entry_num:
581
 
                        paths.setdefault(last_dir_name, []).append(last_fields)
 
706
                        paths.setdefault(last_path, []).append(last_fields)
582
707
                    for num in xrange(first_entry_num+1, last_entry_num):
583
708
                        # TODO: jam 20070223 We are already splitting here, so
584
709
                        #       shouldn't we just split the whole thing rather
585
710
                        #       than doing the split again in add_one_record?
586
711
                        fields = entries[num].split('\0')
587
 
                        dir_name = (fields[1], fields[2])
588
 
                        paths.setdefault(dir_name, []).append(fields)
 
712
                        if fields[1]:
 
713
                            path = fields[1] + '/' + fields[2]
 
714
                        else:
 
715
                            path = fields[2]
 
716
                        paths.setdefault(path, []).append(fields)
589
717
 
590
 
                    for dir_name in middle_files:
591
 
                        for fields in paths.get(dir_name, []):
 
718
                    for path in middle_files:
 
719
                        for fields in paths.get(path, []):
592
720
                            # offset by 1 because of the opening '\0'
593
721
                            # consider changing fields_to_entry to avoid the
594
722
                            # extra list slice
595
723
                            entry = fields_to_entry(fields[1:])
596
 
                            found.setdefault(dir_name, []).append(entry)
 
724
                            found.setdefault(path, []).append(entry)
597
725
 
598
726
            # Now we have split up everything into pre, middle, and post, and
599
727
            # we have handled everything that fell in 'middle'.
616
744
        _bisect_dirblocks is meant to find the contents of directories, which
617
745
        differs from _bisect, which only finds individual entries.
618
746
 
619
 
        :param dir_list: An sorted list of directory names ['', 'dir', 'foo'].
 
747
        :param dir_list: A sorted list of directory names ['', 'dir', 'foo'].
620
748
        :return: A map from dir => entries_for_dir
621
749
        """
622
750
        # TODO: jam 20070223 A lot of the bisecting logic could be shared
629
757
        # If _dirblock_state was in memory, we should just return info from
630
758
        # there, this function is only meant to handle when we want to read
631
759
        # part of the disk.
632
 
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
633
 
 
 
760
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
 
761
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
634
762
        # The disk representation is generally info + '\0\n\0' at the end. But
635
763
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
636
764
        # Because it means we can sync on the '\n'
789
917
 
790
918
        return found
791
919
 
792
 
    def _bisect_recursive(self, dir_name_list):
 
920
    def _bisect_recursive(self, paths):
793
921
        """Bisect for entries for all paths and their children.
794
922
 
795
923
        This will use bisect to find all records for the supplied paths. It
808
936
        # Directories that have been read
809
937
        processed_dirs = set()
810
938
        # Get the ball rolling with the first bisect for all entries.
811
 
        newly_found = self._bisect(dir_name_list)
 
939
        newly_found = self._bisect(paths)
812
940
 
813
941
        while newly_found:
814
942
            # Directories that need to be read
838
966
                            if dir_name[0] in pending_dirs:
839
967
                                # This entry will be found in the dir search
840
968
                                continue
841
 
                            # TODO: We need to check if this entry has
842
 
                            #       already been found. Otherwise we might be
843
 
                            #       hitting infinite recursion.
844
969
                            if dir_name not in found_dir_names:
845
 
                                paths_to_search.add(dir_name)
 
970
                                paths_to_search.add(tree_info[1])
846
971
            # Now we have a list of paths to look for directly, and
847
972
            # directory blocks that need to be read.
848
973
            # newly_found is mixing the keys between (dir, name) and path
853
978
            processed_dirs.update(pending_dirs)
854
979
        return found
855
980
 
 
981
    def _discard_merge_parents(self):
 
982
        """Discard any parents trees beyond the first.
 
983
 
 
984
        Note that if this fails the dirstate is corrupted.
 
985
 
 
986
        After this function returns the dirstate contains 2 trees, neither of
 
987
        which are ghosted.
 
988
        """
 
989
        self._read_header_if_needed()
 
990
        parents = self.get_parent_ids()
 
991
        if len(parents) < 1:
 
992
            return
 
993
        # only require all dirblocks if we are doing a full-pass removal.
 
994
        self._read_dirblocks_if_needed()
 
995
        dead_patterns = set([('a', 'r'), ('a', 'a'), ('r', 'r'), ('r', 'a')])
 
996
        def iter_entries_removable():
 
997
            for block in self._dirblocks:
 
998
                deleted_positions = []
 
999
                for pos, entry in enumerate(block[1]):
 
1000
                    yield entry
 
1001
                    if (entry[1][0][0], entry[1][1][0]) in dead_patterns:
 
1002
                        deleted_positions.append(pos)
 
1003
                if deleted_positions:
 
1004
                    if len(deleted_positions) == len(block[1]):
 
1005
                        del block[1][:]
 
1006
                    else:
 
1007
                        for pos in reversed(deleted_positions):
 
1008
                            del block[1][pos]
 
1009
        # if the first parent is a ghost:
 
1010
        if parents[0] in self.get_ghosts():
 
1011
            empty_parent = [DirState.NULL_PARENT_DETAILS]
 
1012
            for entry in iter_entries_removable():
 
1013
                entry[1][1:] = empty_parent
 
1014
        else:
 
1015
            for entry in iter_entries_removable():
 
1016
                del entry[1][2:]
 
1017
 
 
1018
        self._ghosts = []
 
1019
        self._parents = [parents[0]]
 
1020
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1021
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1022
 
856
1023
    def _empty_parent_info(self):
857
1024
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
858
1025
                                                    len(self._ghosts))
884
1051
        # the basename of the directory must be the end of its full name.
885
1052
        if not (parent_block_index == -1 and
886
1053
            parent_block_index == -1 and dirname == ''):
887
 
            assert dirname.endswith(
888
 
                self._dirblocks[parent_block_index][1][parent_row_index][0][1])
 
1054
            if not dirname.endswith(
 
1055
                    self._dirblocks[parent_block_index][1][parent_row_index][0][1]):
 
1056
                raise AssertionError("bad dirname %r" % dirname)
889
1057
        block_index, present = self._find_block_index_from_key((dirname, '', ''))
890
1058
        if not present:
891
 
            ## In future, when doing partial parsing, this should load and 
 
1059
            ## In future, when doing partial parsing, this should load and
892
1060
            # populate the entire block.
893
1061
            self._dirblocks.insert(block_index, (dirname, []))
894
1062
        return block_index
903
1071
            to prevent unneeded overhead when callers have a sorted list already.
904
1072
        :return: Nothing.
905
1073
        """
906
 
        assert new_entries[0][0][0:2] == ('', ''), \
907
 
            "Missing root row %r" % (new_entries[0][0],)
908
 
        # The two blocks here are deliberate: the root block and the 
 
1074
        if new_entries[0][0][0:2] != ('', ''):
 
1075
            raise AssertionError(
 
1076
                "Missing root row %r" % (new_entries[0][0],))
 
1077
        # The two blocks here are deliberate: the root block and the
909
1078
        # contents-of-root block.
910
1079
        self._dirblocks = [('', []), ('', [])]
911
1080
        current_block = self._dirblocks[0][1]
932
1101
        # The above loop leaves the "root block" entries mixed with the
933
1102
        # "contents-of-root block". But we don't want an if check on
934
1103
        # all entries, so instead we just fix it up here.
935
 
        assert self._dirblocks[1] == ('', [])
 
1104
        if self._dirblocks[1] != ('', []):
 
1105
            raise ValueError("bad dirblock start %r" % (self._dirblocks[1],))
936
1106
        root_block = []
937
1107
        contents_of_root_block = []
938
1108
        for entry in self._dirblocks[0][1]:
943
1113
        self._dirblocks[0] = ('', root_block)
944
1114
        self._dirblocks[1] = ('', contents_of_root_block)
945
1115
 
 
1116
    def _entries_for_path(self, path):
 
1117
        """Return a list with all the entries that match path for all ids."""
 
1118
        dirname, basename = os.path.split(path)
 
1119
        key = (dirname, basename, '')
 
1120
        block_index, present = self._find_block_index_from_key(key)
 
1121
        if not present:
 
1122
            # the block which should contain path is absent.
 
1123
            return []
 
1124
        result = []
 
1125
        block = self._dirblocks[block_index][1]
 
1126
        entry_index, _ = self._find_entry_index(key, block)
 
1127
        # we may need to look at multiple entries at this path: walk while the specific_files match.
 
1128
        while (entry_index < len(block) and
 
1129
            block[entry_index][0][0:2] == key[0:2]):
 
1130
            result.append(block[entry_index])
 
1131
            entry_index += 1
 
1132
        return result
 
1133
 
946
1134
    def _entry_to_line(self, entry):
947
1135
        """Serialize entry to a NULL delimited line ready for _get_output_lines.
948
1136
 
1004
1192
        """
1005
1193
        if key[0:2] == ('', ''):
1006
1194
            return 0, True
 
1195
        try:
 
1196
            if (self._last_block_index is not None and
 
1197
                self._dirblocks[self._last_block_index][0] == key[0]):
 
1198
                return self._last_block_index, True
 
1199
        except IndexError:
 
1200
            pass
1007
1201
        block_index = bisect_dirblock(self._dirblocks, key[0], 1,
1008
1202
                                      cache=self._split_path_cache)
1009
1203
        # _right returns one-past-where-key is so we have to subtract
1010
1204
        # one to use it. we use _right here because there are two
1011
1205
        # '' blocks - the root, and the contents of root
1012
1206
        # we always have a minimum of 2 in self._dirblocks: root and
1013
 
        # root-contents, and for '', we get 2 back, so this is 
 
1207
        # root-contents, and for '', we get 2 back, so this is
1014
1208
        # simple and correct:
1015
1209
        present = (block_index < len(self._dirblocks) and
1016
1210
            self._dirblocks[block_index][0] == key[0])
 
1211
        self._last_block_index = block_index
 
1212
        # Reset the entry index cache to the beginning of the block.
 
1213
        self._last_entry_index = -1
1017
1214
        return block_index, present
1018
1215
 
1019
1216
    def _find_entry_index(self, key, block):
1021
1218
 
1022
1219
        :return: The entry index, True if the entry for the key is present.
1023
1220
        """
 
1221
        len_block = len(block)
 
1222
        try:
 
1223
            if self._last_entry_index is not None:
 
1224
                # mini-bisect here.
 
1225
                entry_index = self._last_entry_index + 1
 
1226
                # A hit is when the key is after the last slot, and before or
 
1227
                # equal to the next slot.
 
1228
                if ((entry_index > 0 and block[entry_index - 1][0] < key) and
 
1229
                    key <= block[entry_index][0]):
 
1230
                    self._last_entry_index = entry_index
 
1231
                    present = (block[entry_index][0] == key)
 
1232
                    return entry_index, present
 
1233
        except IndexError:
 
1234
            pass
1024
1235
        entry_index = bisect.bisect_left(block, (key, []))
1025
 
        present = (entry_index < len(block) and
 
1236
        present = (entry_index < len_block and
1026
1237
            block[entry_index][0] == key)
 
1238
        self._last_entry_index = entry_index
1027
1239
        return entry_index, present
1028
1240
 
1029
1241
    @staticmethod
1030
 
    def from_tree(tree, dir_state_filename):
 
1242
    def from_tree(tree, dir_state_filename, sha1_provider=None):
1031
1243
        """Create a dirstate from a bzr Tree.
1032
1244
 
1033
1245
        :param tree: The tree which should provide parent information and
1034
1246
            inventory ids.
 
1247
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
1248
            If None, a DefaultSHA1Provider is used.
1035
1249
        :return: a DirState object which is currently locked for writing.
1036
1250
            (it was locked by DirState.initialize)
1037
1251
        """
1038
 
        result = DirState.initialize(dir_state_filename)
 
1252
        result = DirState.initialize(dir_state_filename,
 
1253
            sha1_provider=sha1_provider)
1039
1254
        try:
1040
1255
            tree.lock_read()
1041
1256
            try:
1059
1274
            raise
1060
1275
        return result
1061
1276
 
1062
 
    def update_entry(self, entry, abspath, stat_value=None):
1063
 
        """Update the entry based on what is actually on disk.
1064
 
 
1065
 
        :param entry: This is the dirblock entry for the file in question.
1066
 
        :param abspath: The path on disk for this file.
1067
 
        :param stat_value: (optional) if we already have done a stat on the
1068
 
            file, re-use it.
1069
 
        :return: The sha1 hexdigest of the file (40 bytes) or link target of a
1070
 
                symlink.
1071
 
        """
1072
 
        # This code assumes that the entry passed in is directly held in one of
1073
 
        # the internal _dirblocks. So the dirblock state must have already been
1074
 
        # read.
1075
 
        assert self._dirblock_state != DirState.NOT_IN_MEMORY
1076
 
        if stat_value is None:
1077
 
            try:
1078
 
                # We could inline os.lstat but the common case is that
1079
 
                # stat_value will be passed in, not read here.
1080
 
                stat_value = self._lstat(abspath, entry)
1081
 
            except (OSError, IOError), e:
1082
 
                if e.errno in (errno.ENOENT, errno.EACCES,
1083
 
                               errno.EPERM):
1084
 
                    # The entry is missing, consider it gone
1085
 
                    return None
1086
 
                raise
1087
 
 
1088
 
        kind = osutils.file_kind_from_stat_mode(stat_value.st_mode)
 
1277
    def update_by_delta(self, delta):
 
1278
        """Apply an inventory delta to the dirstate for tree 0
 
1279
 
 
1280
        :param delta: An inventory delta.  See Inventory.apply_delta for
 
1281
            details.
 
1282
        """
 
1283
        self._read_dirblocks_if_needed()
 
1284
        insertions = {}
 
1285
        removals = {}
 
1286
        for old_path, new_path, file_id, inv_entry in sorted(delta, reverse=True):
 
1287
            if (file_id in insertions) or (file_id in removals):
 
1288
                raise AssertionError("repeated file id in delta %r" % (file_id,))
 
1289
            if old_path is not None:
 
1290
                old_path = old_path.encode('utf-8')
 
1291
                removals[file_id] = old_path
 
1292
            if new_path is not None:
 
1293
                new_path = new_path.encode('utf-8')
 
1294
                dirname, basename = osutils.split(new_path)
 
1295
                key = (dirname, basename, file_id)
 
1296
                minikind = DirState._kind_to_minikind[inv_entry.kind]
 
1297
                if minikind == 't':
 
1298
                    fingerprint = inv_entry.reference_revision
 
1299
                else:
 
1300
                    fingerprint = ''
 
1301
                insertions[file_id] = (key, minikind, inv_entry.executable,
 
1302
                                       fingerprint, new_path)
 
1303
            # Transform moves into delete+add pairs
 
1304
            if None not in (old_path, new_path):
 
1305
                for child in self._iter_child_entries(0, old_path):
 
1306
                    if child[0][2] in insertions or child[0][2] in removals:
 
1307
                        continue
 
1308
                    child_dirname = child[0][0]
 
1309
                    child_basename = child[0][1]
 
1310
                    minikind = child[1][0][0]
 
1311
                    fingerprint = child[1][0][4]
 
1312
                    executable = child[1][0][3]
 
1313
                    old_child_path = osutils.pathjoin(child[0][0],
 
1314
                                                      child[0][1])
 
1315
                    removals[child[0][2]] = old_child_path
 
1316
                    child_suffix = child_dirname[len(old_path):]
 
1317
                    new_child_dirname = (new_path + child_suffix)
 
1318
                    key = (new_child_dirname, child_basename, child[0][2])
 
1319
                    new_child_path = os.path.join(new_child_dirname,
 
1320
                                                  child_basename)
 
1321
                    insertions[child[0][2]] = (key, minikind, executable,
 
1322
                                               fingerprint, new_child_path)
 
1323
        self._apply_removals(removals.values())
 
1324
        self._apply_insertions(insertions.values())
 
1325
 
 
1326
    def _apply_removals(self, removals):
 
1327
        for path in sorted(removals, reverse=True):
 
1328
            dirname, basename = osutils.split(path)
 
1329
            block_i, entry_i, d_present, f_present = \
 
1330
                self._get_block_entry_index(dirname, basename, 0)
 
1331
            entry = self._dirblocks[block_i][1][entry_i]
 
1332
            self._make_absent(entry)
 
1333
            # See if we have a malformed delta: deleting a directory must not
 
1334
            # leave crud behind. This increases the number of bisects needed
 
1335
            # substantially, but deletion or renames of large numbers of paths
 
1336
            # is rare enough it shouldn't be an issue (famous last words?) RBC
 
1337
            # 20080730.
 
1338
            block_i, entry_i, d_present, f_present = \
 
1339
                self._get_block_entry_index(path, '', 0)
 
1340
            if d_present:
 
1341
                # The dir block is still present in the dirstate; this could
 
1342
                # be due to it being in a parent tree, or a corrupt delta.
 
1343
                for child_entry in self._dirblocks[block_i][1]:
 
1344
                    if child_entry[1][0][0] not in ('r', 'a'):
 
1345
                        raise errors.InconsistentDelta(path, entry[0][2],
 
1346
                            "The file id was deleted but its children were "
 
1347
                            "not deleted.")
 
1348
 
 
1349
    def _apply_insertions(self, adds):
 
1350
        for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
 
1351
            self.update_minimal(key, minikind, executable, fingerprint,
 
1352
                                path_utf8=path_utf8)
 
1353
 
 
1354
    def update_basis_by_delta(self, delta, new_revid):
 
1355
        """Update the parents of this tree after a commit.
 
1356
 
 
1357
        This gives the tree one parent, with revision id new_revid. The
 
1358
        inventory delta is applied to the current basis tree to generate the
 
1359
        inventory for the parent new_revid, and all other parent trees are
 
1360
        discarded.
 
1361
 
 
1362
        Note that an exception during the operation of this method will leave
 
1363
        the dirstate in a corrupt state where it should not be saved.
 
1364
 
 
1365
        Finally, we expect all changes to be synchronising the basis tree with
 
1366
        the working tree.
 
1367
 
 
1368
        :param new_revid: The new revision id for the trees parent.
 
1369
        :param delta: An inventory delta (see apply_inventory_delta) describing
 
1370
            the changes from the current left most parent revision to new_revid.
 
1371
        """
 
1372
        self._read_dirblocks_if_needed()
 
1373
        self._discard_merge_parents()
 
1374
        if self._ghosts != []:
 
1375
            raise NotImplementedError(self.update_basis_by_delta)
 
1376
        if len(self._parents) == 0:
 
1377
            # setup a blank tree, the most simple way.
 
1378
            empty_parent = DirState.NULL_PARENT_DETAILS
 
1379
            for entry in self._iter_entries():
 
1380
                entry[1].append(empty_parent)
 
1381
            self._parents.append(new_revid)
 
1382
 
 
1383
        self._parents[0] = new_revid
 
1384
 
 
1385
        delta = sorted(delta, reverse=True)
 
1386
        adds = []
 
1387
        changes = []
 
1388
        deletes = []
 
1389
        # The paths this function accepts are unicode and must be encoded as we
 
1390
        # go.
 
1391
        encode = cache_utf8.encode
 
1392
        inv_to_entry = self._inv_entry_to_details
 
1393
        # delta is now (deletes, changes), (adds) in reverse lexographical
 
1394
        # order.
 
1395
        # deletes in reverse lexographic order are safe to process in situ.
 
1396
        # renames are not, as a rename from any path could go to a path
 
1397
        # lexographically lower, so we transform renames into delete, add pairs,
 
1398
        # expanding them recursively as needed.
 
1399
        # At the same time, to reduce interface friction we convert the input
 
1400
        # inventory entries to dirstate.
 
1401
        root_only = ('', '')
 
1402
        for old_path, new_path, file_id, inv_entry in delta:
 
1403
            if old_path is None:
 
1404
                adds.append((None, encode(new_path), file_id,
 
1405
                    inv_to_entry(inv_entry), True))
 
1406
            elif new_path is None:
 
1407
                deletes.append((encode(old_path), None, file_id, None, True))
 
1408
            elif (old_path, new_path) != root_only:
 
1409
                # Renames:
 
1410
                # Because renames must preserve their children we must have
 
1411
                # processed all relocations and removes before hand. The sort
 
1412
                # order ensures we've examined the child paths, but we also
 
1413
                # have to execute the removals, or the split to an add/delete
 
1414
                # pair will result in the deleted item being reinserted, or
 
1415
                # renamed items being reinserted twice - and possibly at the
 
1416
                # wrong place. Splitting into a delete/add pair also simplifies
 
1417
                # the handling of entries with ('f', ...), ('r' ...) because
 
1418
                # the target of the 'r' is old_path here, and we add that to
 
1419
                # deletes, meaning that the add handler does not need to check
 
1420
                # for 'r' items on every pass.
 
1421
                self._update_basis_apply_deletes(deletes)
 
1422
                deletes = []
 
1423
                new_path_utf8 = encode(new_path)
 
1424
                # Split into an add/delete pair recursively.
 
1425
                adds.append((None, new_path_utf8, file_id,
 
1426
                    inv_to_entry(inv_entry), False))
 
1427
                # Expunge deletes that we've seen so that deleted/renamed
 
1428
                # children of a rename directory are handled correctly.
 
1429
                new_deletes = reversed(list(self._iter_child_entries(1,
 
1430
                    encode(old_path))))
 
1431
                # Remove the current contents of the tree at orig_path, and
 
1432
                # reinsert at the correct new path.
 
1433
                for entry in new_deletes:
 
1434
                    if entry[0][0]:
 
1435
                        source_path = entry[0][0] + '/' + entry[0][1]
 
1436
                    else:
 
1437
                        source_path = entry[0][1]
 
1438
                    if new_path_utf8:
 
1439
                        target_path = new_path_utf8 + source_path[len(old_path):]
 
1440
                    else:
 
1441
                        if old_path == '':
 
1442
                            raise AssertionError("cannot rename directory to"
 
1443
                                " itself")
 
1444
                        target_path = source_path[len(old_path) + 1:]
 
1445
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
 
1446
                    deletes.append(
 
1447
                        (source_path, target_path, entry[0][2], None, False))
 
1448
                deletes.append(
 
1449
                    (encode(old_path), new_path, file_id, None, False))
 
1450
            else:
 
1451
                # changes to just the root should not require remove/insertion
 
1452
                # of everything.
 
1453
                changes.append((encode(old_path), encode(new_path), file_id,
 
1454
                    inv_to_entry(inv_entry)))
 
1455
 
 
1456
        # Finish expunging deletes/first half of renames.
 
1457
        self._update_basis_apply_deletes(deletes)
 
1458
        # Reinstate second half of renames and new paths.
 
1459
        self._update_basis_apply_adds(adds)
 
1460
        # Apply in-situ changes.
 
1461
        self._update_basis_apply_changes(changes)
 
1462
 
 
1463
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1464
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1465
        self._id_index = None
 
1466
        return
 
1467
 
 
1468
    def _update_basis_apply_adds(self, adds):
 
1469
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
 
1470
 
 
1471
        They may be adds, or renames that have been split into add/delete
 
1472
        pairs.
 
1473
 
 
1474
        :param adds: A sequence of adds. Each add is a tuple:
 
1475
            (None, new_path_utf8, file_id, (entry_details), real_add). real_add
 
1476
            is False when the add is the second half of a remove-and-reinsert
 
1477
            pair created to handle renames and deletes.
 
1478
        """
 
1479
        # Adds are accumulated partly from renames, so can be in any input
 
1480
        # order - sort it.
 
1481
        adds.sort()
 
1482
        # adds is now in lexographic order, which places all parents before
 
1483
        # their children, so we can process it linearly.
 
1484
        absent = 'ar'
 
1485
        for old_path, new_path, file_id, new_details, real_add in adds:
 
1486
            # the entry for this file_id must be in tree 0.
 
1487
            entry = self._get_entry(0, file_id, new_path)
 
1488
            if entry[0] is None or entry[0][2] != file_id:
 
1489
                self._changes_aborted = True
 
1490
                raise errors.InconsistentDelta(new_path, file_id,
 
1491
                    'working tree does not contain new entry')
 
1492
            if real_add and entry[1][1][0] not in absent:
 
1493
                self._changes_aborted = True
 
1494
                raise errors.InconsistentDelta(new_path, file_id,
 
1495
                    'The entry was considered to be a genuinely new record,'
 
1496
                    ' but there was already an old record for it.')
 
1497
            # We don't need to update the target of an 'r' because the handling
 
1498
            # of renames turns all 'r' situations into a delete at the original
 
1499
            # location.
 
1500
            entry[1][1] = new_details
 
1501
 
 
1502
    def _update_basis_apply_changes(self, changes):
 
1503
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
 
1504
 
 
1505
        :param adds: A sequence of changes. Each change is a tuple:
 
1506
            (path_utf8, path_utf8, file_id, (entry_details))
 
1507
        """
 
1508
        absent = 'ar'
 
1509
        for old_path, new_path, file_id, new_details in changes:
 
1510
            # the entry for this file_id must be in tree 0.
 
1511
            entry = self._get_entry(0, file_id, new_path)
 
1512
            if entry[0] is None or entry[0][2] != file_id:
 
1513
                self._changes_aborted = True
 
1514
                raise errors.InconsistentDelta(new_path, file_id,
 
1515
                    'working tree does not contain new entry')
 
1516
            if (entry[1][0][0] in absent or
 
1517
                entry[1][1][0] in absent):
 
1518
                self._changes_aborted = True
 
1519
                raise errors.InconsistentDelta(new_path, file_id,
 
1520
                    'changed considered absent')
 
1521
            entry[1][1] = new_details
 
1522
 
 
1523
    def _update_basis_apply_deletes(self, deletes):
 
1524
        """Apply a sequence of deletes to tree 1 during update_basis_by_delta.
 
1525
 
 
1526
        They may be deletes, or renames that have been split into add/delete
 
1527
        pairs.
 
1528
 
 
1529
        :param deletes: A sequence of deletes. Each delete is a tuple:
 
1530
            (old_path_utf8, new_path_utf8, file_id, None, real_delete).
 
1531
            real_delete is True when the desired outcome is an actual deletion
 
1532
            rather than the rename handling logic temporarily deleting a path
 
1533
            during the replacement of a parent.
 
1534
        """
 
1535
        null = DirState.NULL_PARENT_DETAILS
 
1536
        for old_path, new_path, file_id, _, real_delete in deletes:
 
1537
            if real_delete != (new_path is None):
 
1538
                raise AssertionError("bad delete delta")
 
1539
            # the entry for this file_id must be in tree 1.
 
1540
            dirname, basename = osutils.split(old_path)
 
1541
            block_index, entry_index, dir_present, file_present = \
 
1542
                self._get_block_entry_index(dirname, basename, 1)
 
1543
            if not file_present:
 
1544
                self._changes_aborted = True
 
1545
                raise errors.InconsistentDelta(old_path, file_id,
 
1546
                    'basis tree does not contain removed entry')
 
1547
            entry = self._dirblocks[block_index][1][entry_index]
 
1548
            if entry[0][2] != file_id:
 
1549
                self._changes_aborted = True
 
1550
                raise errors.InconsistentDelta(old_path, file_id,
 
1551
                    'mismatched file_id in tree 1')
 
1552
            if real_delete:
 
1553
                if entry[1][0][0] != 'a':
 
1554
                    self._changes_aborted = True
 
1555
                    raise errors.InconsistentDelta(old_path, file_id,
 
1556
                            'This was marked as a real delete, but the WT state'
 
1557
                            ' claims that it still exists and is versioned.')
 
1558
                del self._dirblocks[block_index][1][entry_index]
 
1559
            else:
 
1560
                if entry[1][0][0] == 'a':
 
1561
                    self._changes_aborted = True
 
1562
                    raise errors.InconsistentDelta(old_path, file_id,
 
1563
                        'The entry was considered a rename, but the source path'
 
1564
                        ' is marked as absent.')
 
1565
                    # For whatever reason, we were asked to rename an entry
 
1566
                    # that was originally marked as deleted. This could be
 
1567
                    # because we are renaming the parent directory, and the WT
 
1568
                    # current state has the file marked as deleted.
 
1569
                elif entry[1][0][0] == 'r':
 
1570
                    # implement the rename
 
1571
                    del self._dirblocks[block_index][1][entry_index]
 
1572
                else:
 
1573
                    # it is being resurrected here, so blank it out temporarily.
 
1574
                    self._dirblocks[block_index][1][entry_index][1][1] = null
 
1575
 
 
1576
    def _observed_sha1(self, entry, sha1, stat_value,
 
1577
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
 
1578
        """Note the sha1 of a file.
 
1579
 
 
1580
        :param entry: The entry the sha1 is for.
 
1581
        :param sha1: The observed sha1.
 
1582
        :param stat_value: The os.lstat for the file.
 
1583
        """
1089
1584
        try:
1090
 
            minikind = DirState._kind_to_minikind[kind]
1091
 
        except KeyError: # Unknown kind
 
1585
            minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
 
1586
        except KeyError:
 
1587
            # Unhandled kind
1092
1588
            return None
1093
 
        packed_stat = pack_stat(stat_value)
1094
 
        (saved_minikind, saved_link_or_sha1, saved_file_size,
1095
 
         saved_executable, saved_packed_stat) = entry[1][0]
1096
 
 
1097
 
        if (minikind == saved_minikind
1098
 
            and packed_stat == saved_packed_stat
1099
 
            # size should also be in packed_stat
1100
 
            and saved_file_size == stat_value.st_size):
1101
 
            # The stat hasn't changed since we saved, so we can potentially
1102
 
            # re-use the saved sha hash.
1103
 
            if minikind == 'd':
1104
 
                return None
1105
 
 
 
1589
        packed_stat = _pack_stat(stat_value)
 
1590
        if minikind == 'f':
1106
1591
            if self._cutoff_time is None:
1107
1592
                self._sha_cutoff_time()
1108
 
 
1109
1593
            if (stat_value.st_mtime < self._cutoff_time
1110
1594
                and stat_value.st_ctime < self._cutoff_time):
1111
 
                # Return the existing fingerprint
1112
 
                return saved_link_or_sha1
1113
 
 
1114
 
        # If we have gotten this far, that means that we need to actually
1115
 
        # process this entry.
1116
 
        link_or_sha1 = None
1117
 
        if minikind == 'f':
1118
 
            link_or_sha1 = self._sha1_file(abspath, entry)
1119
 
            executable = self._is_executable(stat_value.st_mode,
1120
 
                                             saved_executable)
1121
 
            entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
1122
 
                           executable, packed_stat)
1123
 
        elif minikind == 'd':
1124
 
            link_or_sha1 = None
1125
 
            entry[1][0] = ('d', '', 0, False, packed_stat)
1126
 
            if saved_minikind != 'd':
1127
 
                # This changed from something into a directory. Make sure we
1128
 
                # have a directory block for it. This doesn't happen very
1129
 
                # often, so this doesn't have to be super fast.
1130
 
                block_index, entry_index, dir_present, file_present = \
1131
 
                    self._get_block_entry_index(entry[0][0], entry[0][1], 0)
1132
 
                self._ensure_block(block_index, entry_index,
1133
 
                                   osutils.pathjoin(entry[0][0], entry[0][1]))
1134
 
        elif minikind == 'l':
1135
 
            link_or_sha1 = self._read_link(abspath, saved_link_or_sha1)
1136
 
            entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
1137
 
                           False, packed_stat)
1138
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1139
 
        return link_or_sha1
 
1595
                entry[1][0] = ('f', sha1, entry[1][0][2], entry[1][0][3],
 
1596
                    packed_stat)
 
1597
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1140
1598
 
1141
1599
    def _sha_cutoff_time(self):
1142
1600
        """Return cutoff time.
1155
1613
        """Return the os.lstat value for this path."""
1156
1614
        return os.lstat(abspath)
1157
1615
 
1158
 
    def _sha1_file(self, abspath, entry):
1159
 
        """Calculate the SHA1 of a file by reading the full text"""
1160
 
        f = file(abspath, 'rb', buffering=65000)
1161
 
        try:
1162
 
            return osutils.sha_file(f)
1163
 
        finally:
1164
 
            f.close()
 
1616
    def _sha1_file_and_mutter(self, abspath):
 
1617
        # when -Dhashcache is turned on, this is monkey-patched in to log
 
1618
        # file reads
 
1619
        trace.mutter("dirstate sha1 " + abspath)
 
1620
        return self._sha1_provider.sha1(abspath)
1165
1621
 
1166
1622
    def _is_executable(self, mode, old_executable):
1167
1623
        """Is this file executable?"""
1180
1636
        #       already in memory. However, this really needs to be done at a
1181
1637
        #       higher level, because there either won't be anything on disk,
1182
1638
        #       or the thing on disk will be a file.
1183
 
        return os.readlink(abspath)
 
1639
        fs_encoding = osutils._fs_enc
 
1640
        if isinstance(abspath, unicode):
 
1641
            # abspath is defined as the path to pass to lstat. readlink is
 
1642
            # buggy in python < 2.6 (it doesn't encode unicode path into FS
 
1643
            # encoding), so we need to encode ourselves knowing that unicode
 
1644
            # paths are produced by UnicodeDirReader on purpose.
 
1645
            abspath = abspath.encode(fs_encoding)
 
1646
        target = os.readlink(abspath)
 
1647
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
 
1648
            # Change encoding if needed
 
1649
            target = target.decode(fs_encoding).encode('UTF-8')
 
1650
        return target
1184
1651
 
1185
1652
    def get_ghosts(self):
1186
1653
        """Return a list of the parent tree revision ids that are ghosts."""
1304
1771
            be attempted.
1305
1772
        :return: A tuple describing where the path is located, or should be
1306
1773
            inserted. The tuple contains four fields: the block index, the row
1307
 
            index, anda two booleans are True when the directory is present, and
1308
 
            when the entire path is present.  There is no guarantee that either
 
1774
            index, the directory is present (boolean), the entire path is
 
1775
            present (boolean).  There is no guarantee that either
1309
1776
            coordinate is currently reachable unless the found field for it is
1310
1777
            True. For instance, a directory not present in the searched tree
1311
1778
            may be returned with a value one greater than the current highest
1323
1790
            return block_index, 0, False, False
1324
1791
        block = self._dirblocks[block_index][1] # access the entries only
1325
1792
        entry_index, present = self._find_entry_index(key, block)
1326
 
        # linear search through present entries at this path to find the one
 
1793
        # linear search through entries at this path to find the one
1327
1794
        # requested.
1328
1795
        while entry_index < len(block) and block[entry_index][0][1] == basename:
1329
 
            if block[entry_index][1][tree_index][0] not in \
1330
 
                       ('a', 'r'): # absent, relocated
 
1796
            if block[entry_index][1][tree_index][0] not in 'ar':
 
1797
                # neither absent or relocated
1331
1798
                return block_index, entry_index, True, True
1332
1799
            entry_index += 1
1333
1800
        return block_index, entry_index, True, False
1334
1801
 
1335
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None):
1336
 
        """Get the dirstate entry for path in tree tree_index
 
1802
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
1803
        """Get the dirstate entry for path in tree tree_index.
1337
1804
 
1338
1805
        If either file_id or path is supplied, it is used as the key to lookup.
1339
1806
        If both are supplied, the fastest lookup is used, and an error is
1346
1813
            trees.
1347
1814
        :param fileid_utf8: A utf8 file_id to look up.
1348
1815
        :param path_utf8: An utf8 path to be looked up.
 
1816
        :param include_deleted: If True, and performing a lookup via
 
1817
            fileid_utf8 rather than path_utf8, return an entry for deleted
 
1818
            (absent) paths.
1349
1819
        :return: The dirstate entry tuple for path, or (None, None)
1350
1820
        """
1351
1821
        self._read_dirblocks_if_needed()
1352
1822
        if path_utf8 is not None:
1353
 
            assert path_utf8.__class__ == str, 'path_utf8 is not a str: %s %s' % (type(path_utf8), path_utf8)
 
1823
            if type(path_utf8) is not str:
 
1824
                raise AssertionError('path_utf8 is not a str: %s %s'
 
1825
                    % (type(path_utf8), path_utf8))
1354
1826
            # path lookups are faster
1355
1827
            dirname, basename = osutils.split(path_utf8)
1356
1828
            block_index, entry_index, dir_present, file_present = \
1358
1830
            if not file_present:
1359
1831
                return None, None
1360
1832
            entry = self._dirblocks[block_index][1][entry_index]
1361
 
            assert entry[0][2] and entry[1][tree_index][0] not in ('a', 'r'), 'unversioned entry?!?!'
 
1833
            if not (entry[0][2] and entry[1][tree_index][0] not in ('a', 'r')):
 
1834
                raise AssertionError('unversioned entry?')
1362
1835
            if fileid_utf8:
1363
1836
                if entry[0][2] != fileid_utf8:
 
1837
                    self._changes_aborted = True
1364
1838
                    raise errors.BzrError('integrity error ? : mismatching'
1365
1839
                                          ' tree_index, file_id and path')
1366
1840
            return entry
1367
1841
        else:
1368
 
            assert fileid_utf8 is not None
1369
1842
            possible_keys = self._get_id_index().get(fileid_utf8, None)
1370
1843
            if not possible_keys:
1371
1844
                return None, None
1378
1851
                    continue
1379
1852
                # WARNING: DO not change this code to use _get_block_entry_index
1380
1853
                # as that function is not suitable: it does not use the key
1381
 
                # to lookup, and thus the wront coordinates are returned.
 
1854
                # to lookup, and thus the wrong coordinates are returned.
1382
1855
                block = self._dirblocks[block_index][1]
1383
1856
                entry_index, present = self._find_entry_index(key, block)
1384
1857
                if present:
1385
1858
                    entry = self._dirblocks[block_index][1][entry_index]
1386
1859
                    if entry[1][tree_index][0] in 'fdlt':
1387
 
                        # this is the result we are looking for: the  
 
1860
                        # this is the result we are looking for: the
1388
1861
                        # real home of this file_id in this tree.
1389
1862
                        return entry
1390
1863
                    if entry[1][tree_index][0] == 'a':
1391
1864
                        # there is no home for this entry in this tree
 
1865
                        if include_deleted:
 
1866
                            return entry
1392
1867
                        return None, None
1393
 
                    assert entry[1][tree_index][0] == 'r', \
1394
 
                        "entry %r has invalid minikind %r for tree %r" \
1395
 
                        % (entry,
1396
 
                           entry[1][tree_index][0],
1397
 
                           tree_index)
 
1868
                    if entry[1][tree_index][0] != 'r':
 
1869
                        raise AssertionError(
 
1870
                            "entry %r has invalid minikind %r for tree %r" \
 
1871
                            % (entry,
 
1872
                               entry[1][tree_index][0],
 
1873
                               tree_index))
1398
1874
                    real_path = entry[1][tree_index][1]
1399
1875
                    return self._get_entry(tree_index, fileid_utf8=fileid_utf8,
1400
1876
                        path_utf8=real_path)
1401
1877
            return None, None
1402
1878
 
1403
1879
    @classmethod
1404
 
    def initialize(cls, path):
 
1880
    def initialize(cls, path, sha1_provider=None):
1405
1881
        """Create a new dirstate on path.
1406
1882
 
1407
1883
        The new dirstate will be an empty tree - that is it has no parents,
1408
1884
        and only a root node - which has id ROOT_ID.
1409
1885
 
1410
 
        The object will be write locked when returned to the caller,
1411
 
        unless there was an exception in the writing, in which case it
1412
 
        will be unlocked.
1413
 
 
1414
1886
        :param path: The name of the file for the dirstate.
1415
 
        :return: A DirState object.
 
1887
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
1888
            If None, a DefaultSHA1Provider is used.
 
1889
        :return: A write-locked DirState object.
1416
1890
        """
1417
1891
        # This constructs a new DirState object on a path, sets the _state_file
1418
1892
        # to a new empty file for that path. It then calls _set_data() with our
1419
1893
        # stock empty dirstate information - a root with ROOT_ID, no children,
1420
1894
        # and no parents. Finally it calls save() to ensure that this data will
1421
1895
        # persist.
1422
 
        result = cls(path)
 
1896
        if sha1_provider is None:
 
1897
            sha1_provider = DefaultSHA1Provider()
 
1898
        result = cls(path, sha1_provider)
1423
1899
        # root dir and root dir contents with no children.
1424
1900
        empty_tree_dirblocks = [('', []), ('', [])]
1425
1901
        # a new root directory, with a NULLSTAT.
1436
1912
            raise
1437
1913
        return result
1438
1914
 
1439
 
    def _inv_entry_to_details(self, inv_entry):
 
1915
    @staticmethod
 
1916
    def _inv_entry_to_details(inv_entry):
1440
1917
        """Convert an inventory entry (from a revision tree) to state details.
1441
1918
 
1442
1919
        :param inv_entry: An inventory entry whose sha1 and link targets can be
1447
1924
        kind = inv_entry.kind
1448
1925
        minikind = DirState._kind_to_minikind[kind]
1449
1926
        tree_data = inv_entry.revision
1450
 
        assert len(tree_data) > 0, 'empty revision for the inv_entry.'
1451
1927
        if kind == 'directory':
1452
1928
            fingerprint = ''
1453
1929
            size = 0
1454
1930
            executable = False
1455
1931
        elif kind == 'symlink':
1456
 
            fingerprint = inv_entry.symlink_target or ''
 
1932
            if inv_entry.symlink_target is None:
 
1933
                fingerprint = ''
 
1934
            else:
 
1935
                fingerprint = inv_entry.symlink_target.encode('utf8')
1457
1936
            size = 0
1458
1937
            executable = False
1459
1938
        elif kind == 'file':
1468
1947
            raise Exception("can't pack %s" % inv_entry)
1469
1948
        return (minikind, fingerprint, size, executable, tree_data)
1470
1949
 
 
1950
    def _iter_child_entries(self, tree_index, path_utf8):
 
1951
        """Iterate over all the entries that are children of path_utf.
 
1952
 
 
1953
        This only returns entries that are present (not in 'a', 'r') in
 
1954
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
 
1955
        results may differ from that obtained if paths were statted to
 
1956
        determine what ones were directories.
 
1957
 
 
1958
        Asking for the children of a non-directory will return an empty
 
1959
        iterator.
 
1960
        """
 
1961
        pending_dirs = []
 
1962
        next_pending_dirs = [path_utf8]
 
1963
        absent = 'ar'
 
1964
        while next_pending_dirs:
 
1965
            pending_dirs = next_pending_dirs
 
1966
            next_pending_dirs = []
 
1967
            for path in pending_dirs:
 
1968
                block_index, present = self._find_block_index_from_key(
 
1969
                    (path, '', ''))
 
1970
                if block_index == 0:
 
1971
                    block_index = 1
 
1972
                    if len(self._dirblocks) == 1:
 
1973
                        # asked for the children of the root with no other
 
1974
                        # contents.
 
1975
                        return
 
1976
                if not present:
 
1977
                    # children of a non-directory asked for.
 
1978
                    continue
 
1979
                block = self._dirblocks[block_index]
 
1980
                for entry in block[1]:
 
1981
                    kind = entry[1][tree_index][0]
 
1982
                    if kind not in absent:
 
1983
                        yield entry
 
1984
                    if kind == 'd':
 
1985
                        if entry[0][0]:
 
1986
                            path = entry[0][0] + '/' + entry[0][1]
 
1987
                        else:
 
1988
                            path = entry[0][1]
 
1989
                        next_pending_dirs.append(path)
 
1990
 
1471
1991
    def _iter_entries(self):
1472
1992
        """Iterate over all the entries in the dirstate.
1473
1993
 
1489
2009
        return self._id_index
1490
2010
 
1491
2011
    def _get_output_lines(self, lines):
1492
 
        """format lines for final output.
 
2012
        """Format lines for final output.
1493
2013
 
1494
 
        :param lines: A sequece of lines containing the parents list and the
 
2014
        :param lines: A sequence of lines containing the parents list and the
1495
2015
            path lines.
1496
2016
        """
1497
2017
        output_lines = [DirState.HEADER_FORMAT_3]
1505
2025
        return output_lines
1506
2026
 
1507
2027
    def _make_deleted_row(self, fileid_utf8, parents):
1508
 
        """Return a deleted for for fileid_utf8."""
 
2028
        """Return a deleted row for fileid_utf8."""
1509
2029
        return ('/', 'RECYCLED.BIN', 'file', fileid_utf8, 0, DirState.NULLSTAT,
1510
2030
            ''), parents
1511
2031
 
1514
2034
        return len(self._parents) - len(self._ghosts)
1515
2035
 
1516
2036
    @staticmethod
1517
 
    def on_file(path):
1518
 
        """Construct a DirState on the file at path path.
 
2037
    def on_file(path, sha1_provider=None):
 
2038
        """Construct a DirState on the file at path "path".
1519
2039
 
 
2040
        :param path: The path at which the dirstate file on disk should live.
 
2041
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
2042
            If None, a DefaultSHA1Provider is used.
1520
2043
        :return: An unlocked DirState object, associated with the given path.
1521
2044
        """
1522
 
        result = DirState(path)
 
2045
        if sha1_provider is None:
 
2046
            sha1_provider = DefaultSHA1Provider()
 
2047
        result = DirState(path, sha1_provider)
1523
2048
        return result
1524
2049
 
1525
2050
    def _read_dirblocks_if_needed(self):
1526
2051
        """Read in all the dirblocks from the file if they are not in memory.
1527
 
        
 
2052
 
1528
2053
        This populates self._dirblocks, and sets self._dirblock_state to
1529
2054
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
1530
2055
        loading.
1531
2056
        """
1532
2057
        self._read_header_if_needed()
1533
2058
        if self._dirblock_state == DirState.NOT_IN_MEMORY:
1534
 
            # move the _state_file pointer to after the header (in case bisect
1535
 
            # has been called in the mean time)
1536
 
            self._state_file.seek(self._end_of_header)
1537
 
            text = self._state_file.read()
1538
 
            # TODO: check the crc checksums. crc_measured = zlib.crc32(text)
1539
 
 
1540
 
            fields = text.split('\0')
1541
 
            # Remove the last blank entry
1542
 
            trailing = fields.pop()
1543
 
            assert trailing == ''
1544
 
            # consider turning fields into a tuple.
1545
 
 
1546
 
            # skip the first field which is the trailing null from the header.
1547
 
            cur = 1
1548
 
            # Each line now has an extra '\n' field which is not used
1549
 
            # so we just skip over it
1550
 
            # entry size:
1551
 
            #  3 fields for the key
1552
 
            #  + number of fields per tree_data (5) * tree count
1553
 
            #  + newline
1554
 
            num_present_parents = self._num_present_parents()
1555
 
            tree_count = 1 + num_present_parents
1556
 
            entry_size = self._fields_per_entry()
1557
 
            expected_field_count = entry_size * self._num_entries
1558
 
            field_count = len(fields)
1559
 
            # this checks our adjustment, and also catches file too short.
1560
 
            assert field_count - cur == expected_field_count, \
1561
 
                'field count incorrect %s != %s, entry_size=%s, '\
1562
 
                'num_entries=%s fields=%r' % (
1563
 
                    field_count - cur, expected_field_count, entry_size,
1564
 
                    self._num_entries, fields)
1565
 
 
1566
 
            if num_present_parents == 1:
1567
 
                # Bind external functions to local names
1568
 
                _int = int
1569
 
                # We access all fields in order, so we can just iterate over
1570
 
                # them. Grab an straight iterator over the fields. (We use an
1571
 
                # iterator because we don't want to do a lot of additions, nor
1572
 
                # do we want to do a lot of slicing)
1573
 
                next = iter(fields).next
1574
 
                # Move the iterator to the current position
1575
 
                for x in xrange(cur):
1576
 
                    next()
1577
 
                # The two blocks here are deliberate: the root block and the
1578
 
                # contents-of-root block.
1579
 
                self._dirblocks = [('', []), ('', [])]
1580
 
                current_block = self._dirblocks[0][1]
1581
 
                current_dirname = ''
1582
 
                append_entry = current_block.append
1583
 
                for count in xrange(self._num_entries):
1584
 
                    dirname = next()
1585
 
                    name = next()
1586
 
                    file_id = next()
1587
 
                    if dirname != current_dirname:
1588
 
                        # new block - different dirname
1589
 
                        current_block = []
1590
 
                        current_dirname = dirname
1591
 
                        self._dirblocks.append((current_dirname, current_block))
1592
 
                        append_entry = current_block.append
1593
 
                    # we know current_dirname == dirname, so re-use it to avoid
1594
 
                    # creating new strings
1595
 
                    entry = ((current_dirname, name, file_id),
1596
 
                             [(# Current Tree
1597
 
                                 next(),                # minikind
1598
 
                                 next(),                # fingerprint
1599
 
                                 _int(next()),          # size
1600
 
                                 next() == 'y',         # executable
1601
 
                                 next(),                # packed_stat or revision_id
1602
 
                             ),
1603
 
                             ( # Parent 1
1604
 
                                 next(),                # minikind
1605
 
                                 next(),                # fingerprint
1606
 
                                 _int(next()),          # size
1607
 
                                 next() == 'y',         # executable
1608
 
                                 next(),                # packed_stat or revision_id
1609
 
                             ),
1610
 
                             ])
1611
 
                    trailing = next()
1612
 
                    assert trailing == '\n'
1613
 
                    # append the entry to the current block
1614
 
                    append_entry(entry)
1615
 
                self._split_root_dirblock_into_contents()
1616
 
            else:
1617
 
                fields_to_entry = self._get_fields_to_entry()
1618
 
                entries = [fields_to_entry(fields[pos:pos+entry_size])
1619
 
                           for pos in xrange(cur, field_count, entry_size)]
1620
 
                self._entries_to_current_state(entries)
1621
 
            # To convert from format 2  => format 3
1622
 
            # self._dirblocks = sorted(self._dirblocks,
1623
 
            #                          key=lambda blk:blk[0].split('/'))
1624
 
            # To convert from format 3 => format 2
1625
 
            # self._dirblocks = sorted(self._dirblocks)
1626
 
            self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
 
2059
            _read_dirblocks(self)
1627
2060
 
1628
2061
    def _read_header(self):
1629
2062
        """This reads in the metadata header, and the parent ids.
1637
2070
        parent_line = self._state_file.readline()
1638
2071
        info = parent_line.split('\0')
1639
2072
        num_parents = int(info[0])
1640
 
        assert num_parents == len(info)-2, 'incorrect parent info line'
1641
2073
        self._parents = info[1:-1]
1642
 
 
1643
2074
        ghost_line = self._state_file.readline()
1644
2075
        info = ghost_line.split('\0')
1645
2076
        num_ghosts = int(info[1])
1646
 
        assert num_ghosts == len(info)-3, 'incorrect ghost info line'
1647
2077
        self._ghosts = info[2:-1]
1648
2078
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
1649
2079
        self._end_of_header = self._state_file.tell()
1657
2087
            self._read_header()
1658
2088
 
1659
2089
    def _read_prelude(self):
1660
 
        """Read in the prelude header of the dirstate file
 
2090
        """Read in the prelude header of the dirstate file.
1661
2091
 
1662
2092
        This only reads in the stuff that is not connected to the crc
1663
2093
        checksum. The position will be correct to read in the rest of
1666
2096
        and their ids. Followed by a newline.
1667
2097
        """
1668
2098
        header = self._state_file.readline()
1669
 
        assert header == DirState.HEADER_FORMAT_3, \
1670
 
            'invalid header line: %r' % (header,)
 
2099
        if header != DirState.HEADER_FORMAT_3:
 
2100
            raise errors.BzrError(
 
2101
                'invalid header line: %r' % (header,))
1671
2102
        crc_line = self._state_file.readline()
1672
 
        assert crc_line.startswith('crc32: '), 'missing crc32 checksum'
 
2103
        if not crc_line.startswith('crc32: '):
 
2104
            raise errors.BzrError('missing crc32 checksum: %r' % crc_line)
1673
2105
        self.crc_expected = int(crc_line[len('crc32: '):-1])
1674
2106
        num_entries_line = self._state_file.readline()
1675
 
        assert num_entries_line.startswith('num_entries: '), 'missing num_entries line'
 
2107
        if not num_entries_line.startswith('num_entries: '):
 
2108
            raise errors.BzrError('missing num_entries line')
1676
2109
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
1677
2110
 
 
2111
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
 
2112
        """Find a sha1 given a stat lookup."""
 
2113
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
 
2114
 
 
2115
    def _get_packed_stat_index(self):
 
2116
        """Get a packed_stat index of self._dirblocks."""
 
2117
        if self._packed_stat_index is None:
 
2118
            index = {}
 
2119
            for key, tree_details in self._iter_entries():
 
2120
                if tree_details[0][0] == 'f':
 
2121
                    index[tree_details[0][4]] = tree_details[0][1]
 
2122
            self._packed_stat_index = index
 
2123
        return self._packed_stat_index
 
2124
 
1678
2125
    def save(self):
1679
2126
        """Save any pending changes created during this session.
1680
2127
 
1681
2128
        We reuse the existing file, because that prevents race conditions with
1682
2129
        file creation, and use oslocks on it to prevent concurrent modification
1683
 
        and reads - because dirstates incremental data aggretation is not
 
2130
        and reads - because dirstate's incremental data aggregation is not
1684
2131
        compatible with reading a modified file, and replacing a file in use by
1685
 
        another process is impossible on windows.
 
2132
        another process is impossible on Windows.
1686
2133
 
1687
2134
        A dirstate in read only mode should be smart enough though to validate
1688
2135
        that the file has not changed, and otherwise discard its cache and
1689
2136
        start over, to allow for fine grained read lock duration, so 'status'
1690
2137
        wont block 'commit' - for example.
1691
2138
        """
 
2139
        if self._changes_aborted:
 
2140
            # Should this be a warning? For now, I'm expecting that places that
 
2141
            # mark it inconsistent will warn, making a warning here redundant.
 
2142
            trace.mutter('Not saving DirState because '
 
2143
                    '_changes_aborted is set.')
 
2144
            return
1692
2145
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
1693
2146
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
1694
2147
 
1727
2180
 
1728
2181
        :param parent_ids: A list of parent tree revision ids.
1729
2182
        :param dirblocks: A list containing one tuple for each directory in the
1730
 
            tree. Each tuple contains the directory path and a list of entries 
 
2183
            tree. Each tuple contains the directory path and a list of entries
1731
2184
            found in that directory.
1732
2185
        """
1733
2186
        # our memory copy is now authoritative.
1736
2189
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1737
2190
        self._parents = list(parent_ids)
1738
2191
        self._id_index = None
 
2192
        self._packed_stat_index = None
1739
2193
 
1740
2194
    def set_path_id(self, path, new_id):
1741
2195
        """Change the id of path to new_id in the current working tree.
1745
2199
        :param new_id: The new id to assign to the path. This must be a utf8
1746
2200
            file id (not unicode, and not None).
1747
2201
        """
1748
 
        assert new_id.__class__ == str, \
1749
 
            "path_id %r is not a plain string" % (new_id,)
1750
2202
        self._read_dirblocks_if_needed()
1751
2203
        if len(path):
1752
 
            # logic not written
 
2204
            # TODO: logic not written
1753
2205
            raise NotImplementedError(self.set_path_id)
1754
2206
        # TODO: check new id is unique
1755
2207
        entry = self._get_entry(0, path_utf8=path)
1768
2220
        """Set the parent trees for the dirstate.
1769
2221
 
1770
2222
        :param trees: A list of revision_id, tree tuples. tree must be provided
1771
 
            even if the revision_id refers to a ghost: supply an empty tree in 
 
2223
            even if the revision_id refers to a ghost: supply an empty tree in
1772
2224
            this case.
1773
2225
        :param ghosts: A list of the revision_ids that are ghosts at the time
1774
2226
            of setting.
1775
 
        """ 
1776
 
        self._validate()
1777
 
        # TODO: generate a list of parent indexes to preserve to save 
 
2227
        """
 
2228
        # TODO: generate a list of parent indexes to preserve to save
1778
2229
        # processing specific parent trees. In the common case one tree will
1779
2230
        # be preserved - the left most parent.
1780
2231
        # TODO: if the parent tree is a dirstate, we might want to walk them
1785
2236
        # map and then walk the new parent trees only, mapping them into the
1786
2237
        # dirstate. Walk the dirstate at the same time to remove unreferenced
1787
2238
        # entries.
1788
 
        # for now: 
1789
 
        # sketch: loop over all entries in the dirstate, cherry picking 
 
2239
        # for now:
 
2240
        # sketch: loop over all entries in the dirstate, cherry picking
1790
2241
        # entries from the parent trees, if they are not ghost trees.
1791
2242
        # after we finish walking the dirstate, all entries not in the dirstate
1792
2243
        # are deletes, so we want to append them to the end as per the design
1797
2248
        #   links. We dont't trivially use the inventory from other trees
1798
2249
        #   because this leads to either double touching, or to accessing
1799
2250
        #   missing keys,
1800
 
        # - find other keys containing a path 
1801
 
        # We accumulate each entry via this dictionary, including the root 
 
2251
        # - find other keys containing a path
 
2252
        # We accumulate each entry via this dictionary, including the root
1802
2253
        by_path = {}
1803
2254
        id_index = {}
1804
2255
        # we could do parallel iterators, but because file id data may be
1808
2259
        # parent, but for now the common cases are adding a new parent (merge),
1809
2260
        # and replacing completely (commit), and commit is more common: so
1810
2261
        # optimise merge later.
1811
 
        
 
2262
 
1812
2263
        # ---- start generation of full tree mapping data
1813
2264
        # what trees should we use?
1814
2265
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
1815
 
        # how many trees do we end up with 
 
2266
        # how many trees do we end up with
1816
2267
        parent_count = len(parent_trees)
1817
2268
 
1818
2269
        # one: the current tree
1819
2270
        for entry in self._iter_entries():
1820
2271
            # skip entries not in the current tree
1821
 
            if entry[1][0][0] in ('a', 'r'): # absent, relocated
 
2272
            if entry[1][0][0] in 'ar': # absent, relocated
1822
2273
                continue
1823
2274
            by_path[entry[0]] = [entry[1][0]] + \
1824
2275
                [DirState.NULL_PARENT_DETAILS] * parent_count
1825
2276
            id_index[entry[0][2]] = set([entry[0]])
1826
 
        
 
2277
 
1827
2278
        # now the parent trees:
1828
2279
        for tree_index, tree in enumerate(parent_trees):
1829
2280
            # the index is off by one, adjust it.
1843
2294
                # avoid checking all known paths for the id when generating a
1844
2295
                # new entry at this path: by adding the id->path mapping last,
1845
2296
                # all the mappings are valid and have correct relocation
1846
 
                # records where needed. 
 
2297
                # records where needed.
1847
2298
                file_id = entry.file_id
1848
2299
                path_utf8 = path.encode('utf8')
1849
2300
                dirname, basename = osutils.split(path_utf8)
1858
2309
                        # this file id is at a different path in one of the
1859
2310
                        # other trees, so put absent pointers there
1860
2311
                        # This is the vertical axis in the matrix, all pointing
1861
 
                        # tot he real path.
 
2312
                        # to the real path.
1862
2313
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
1863
 
                # by path consistency: Insert into an existing path record (trivial), or 
 
2314
                # by path consistency: Insert into an existing path record (trivial), or
1864
2315
                # add a new one with relocation pointers for the other tree indexes.
1865
2316
                if new_entry_key in id_index[file_id]:
1866
2317
                    # there is already an entry where this data belongs, just insert it.
1879
2330
                            new_details.append(DirState.NULL_PARENT_DETAILS)
1880
2331
                        else:
1881
2332
                            # grab any one entry, use it to find the right path.
1882
 
                            # TODO: optimise this to reduce memory use in highly 
 
2333
                            # TODO: optimise this to reduce memory use in highly
1883
2334
                            # fragmented situations by reusing the relocation
1884
2335
                            # records.
1885
2336
                            a_key = iter(id_index[file_id]).next()
1904
2355
        self._header_state = DirState.IN_MEMORY_MODIFIED
1905
2356
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1906
2357
        self._id_index = id_index
1907
 
        self._validate()
1908
2358
 
1909
2359
    def _sort_entries(self, entry_list):
1910
2360
        """Given a list of entries, sort them into the right order.
1913
2363
        try to keep everything in sorted blocks all the time, but sometimes
1914
2364
        it's easier to sort after the fact.
1915
2365
        """
1916
 
        # TODO: Might be faster to do a schwartzian transform?
1917
2366
        def _key(entry):
1918
2367
            # sort by: directory parts, file name, file id
1919
2368
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
1920
2369
        return sorted(entry_list, key=_key)
1921
2370
 
1922
2371
    def set_state_from_inventory(self, new_inv):
1923
 
        """Set new_inv as the current state. 
 
2372
        """Set new_inv as the current state.
1924
2373
 
1925
2374
        This API is called by tree transform, and will usually occur with
1926
2375
        existing parent trees.
1927
2376
 
1928
2377
        :param new_inv: The inventory object to set current state from.
1929
2378
        """
 
2379
        if 'evil' in debug.debug_flags:
 
2380
            trace.mutter_callsite(1,
 
2381
                "set_state_from_inventory called; please mutate the tree instead")
1930
2382
        self._read_dirblocks_if_needed()
1931
2383
        # sketch:
1932
 
        # incremental algorithm:
1933
 
        # two iterators: current data and new data, both in dirblock order. 
 
2384
        # Two iterators: current data and new data, both in dirblock order.
 
2385
        # We zip them together, which tells about entries that are new in the
 
2386
        # inventory, or removed in the inventory, or present in both and
 
2387
        # possibly changed.
 
2388
        #
 
2389
        # You might think we could just synthesize a new dirstate directly
 
2390
        # since we're processing it in the right order.  However, we need to
 
2391
        # also consider there may be any number of parent trees and relocation
 
2392
        # pointers, and we don't want to duplicate that here.
1934
2393
        new_iterator = new_inv.iter_entries_by_dir()
1935
2394
        # we will be modifying the dirstate, so we need a stable iterator. In
1936
2395
        # future we might write one, for now we just clone the state into a
1937
 
        # list - which is a shallow copy, so each 
 
2396
        # list - which is a shallow copy.
1938
2397
        old_iterator = iter(list(self._iter_entries()))
1939
2398
        # both must have roots so this is safe:
1940
2399
        current_new = new_iterator.next()
1946
2405
                return None
1947
2406
        while current_new or current_old:
1948
2407
            # skip entries in old that are not really there
1949
 
            if current_old and current_old[1][0][0] in ('r', 'a'):
 
2408
            if current_old and current_old[1][0][0] in 'ar':
1950
2409
                # relocated or absent
1951
2410
                current_old = advance(old_iterator)
1952
2411
                continue
1959
2418
                current_new_minikind = \
1960
2419
                    DirState._kind_to_minikind[current_new[1].kind]
1961
2420
                if current_new_minikind == 't':
1962
 
                    fingerprint = current_new[1].reference_revision
 
2421
                    fingerprint = current_new[1].reference_revision or ''
1963
2422
                else:
 
2423
                    # We normally only insert or remove records, or update
 
2424
                    # them when it has significantly changed.  Then we want to
 
2425
                    # erase its fingerprint.  Unaffected records should
 
2426
                    # normally not be updated at all.
1964
2427
                    fingerprint = ''
1965
2428
            else:
1966
2429
                # for safety disable variables
1967
 
                new_path_utf8 = new_dirname = new_basename = new_id = new_entry_key = None
 
2430
                new_path_utf8 = new_dirname = new_basename = new_id = \
 
2431
                    new_entry_key = None
1968
2432
            # 5 cases, we dont have a value that is strictly greater than everything, so
1969
2433
            # we make both end conditions explicit
1970
2434
            if not current_old:
1979
2443
                current_old = advance(old_iterator)
1980
2444
            elif new_entry_key == current_old[0]:
1981
2445
                # same -  common case
 
2446
                # We're looking at the same path and id in both the dirstate
 
2447
                # and inventory, so just need to update the fields in the
 
2448
                # dirstate from the one in the inventory.
1982
2449
                # TODO: update the record if anything significant has changed.
1983
2450
                # the minimal required trigger is if the execute bit or cached
1984
2451
                # kind has changed.
1990
2457
                # both sides are dealt with, move on
1991
2458
                current_old = advance(old_iterator)
1992
2459
                current_new = advance(new_iterator)
1993
 
            elif new_entry_key < current_old[0]:
 
2460
            elif (cmp_by_dirs(new_dirname, current_old[0][0]) < 0
 
2461
                  or (new_dirname == current_old[0][0]
 
2462
                      and new_entry_key[1:] < current_old[0][1:])):
1994
2463
                # new comes before:
1995
2464
                # add a entry for this and advance new
1996
2465
                self.update_minimal(new_entry_key, current_new_minikind,
1998
2467
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
1999
2468
                current_new = advance(new_iterator)
2000
2469
            else:
2001
 
                # old comes before:
 
2470
                # we've advanced past the place where the old key would be,
 
2471
                # without seeing it in the new list.  so it must be gone.
2002
2472
                self._make_absent(current_old)
2003
2473
                current_old = advance(old_iterator)
2004
2474
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2005
2475
        self._id_index = None
 
2476
        self._packed_stat_index = None
2006
2477
 
2007
2478
    def _make_absent(self, current_old):
2008
2479
        """Mark current_old - an entry - as absent for tree 0.
2009
2480
 
2010
 
        :return: True if this was the last details entry for they entry key:
 
2481
        :return: True if this was the last details entry for the entry key:
2011
2482
            that is, if the underlying block has had the entry removed, thus
2012
2483
            shrinking in length.
2013
2484
        """
2014
2485
        # build up paths that this id will be left at after the change is made,
2015
2486
        # so we can update their cross references in tree 0
2016
2487
        all_remaining_keys = set()
2017
 
        # Dont check the working tree, because its going.
 
2488
        # Dont check the working tree, because it's going.
2018
2489
        for details in current_old[1][1:]:
2019
 
            if details[0] not in ('a', 'r'): # absent, relocated
 
2490
            if details[0] not in 'ar': # absent, relocated
2020
2491
                all_remaining_keys.add(current_old[0])
2021
2492
            elif details[0] == 'r': # relocated
2022
2493
                # record the key for the real path.
2029
2500
            # Remove it, its meaningless.
2030
2501
            block = self._find_block(current_old[0])
2031
2502
            entry_index, present = self._find_entry_index(current_old[0], block[1])
2032
 
            assert present, 'could not find entry for %s' % (current_old,)
 
2503
            if not present:
 
2504
                raise AssertionError('could not find entry for %s' % (current_old,))
2033
2505
            block[1].pop(entry_index)
2034
2506
            # if we have an id_index in use, remove this key from it for this id.
2035
2507
            if self._id_index is not None:
2036
2508
                self._id_index[current_old[0][2]].remove(current_old[0])
2037
2509
        # update all remaining keys for this id to record it as absent. The
2038
 
        # existing details may either be the record we are making as deleted
 
2510
        # existing details may either be the record we are marking as deleted
2039
2511
        # (if there were other trees with the id present at this path), or may
2040
2512
        # be relocations.
2041
2513
        for update_key in all_remaining_keys:
2042
2514
            update_block_index, present = \
2043
2515
                self._find_block_index_from_key(update_key)
2044
 
            assert present, 'could not find block for %s' % (update_key,)
 
2516
            if not present:
 
2517
                raise AssertionError('could not find block for %s' % (update_key,))
2045
2518
            update_entry_index, present = \
2046
2519
                self._find_entry_index(update_key, self._dirblocks[update_block_index][1])
2047
 
            assert present, 'could not find entry for %s' % (update_key,)
 
2520
            if not present:
 
2521
                raise AssertionError('could not find entry for %s' % (update_key,))
2048
2522
            update_tree_details = self._dirblocks[update_block_index][1][update_entry_index][1]
2049
2523
            # it must not be absent at the moment
2050
 
            assert update_tree_details[0][0] != 'a' # absent
 
2524
            if update_tree_details[0][0] == 'a': # absent
 
2525
                raise AssertionError('bad row %r' % (update_tree_details,))
2051
2526
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2052
2527
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2053
2528
        return last_reference
2064
2539
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
2065
2540
                'directory'), etc.
2066
2541
        :param executable: Should the executable bit be set?
2067
 
        :param fingerprint: Simple fingerprint for new entry.
2068
 
        :param packed_stat: packed stat value for new entry.
 
2542
        :param fingerprint: Simple fingerprint for new entry: canonical-form
 
2543
            sha1 for files, referenced revision id for subtrees, etc.
 
2544
        :param packed_stat: Packed stat value for new entry.
2069
2545
        :param size: Size information for new entry
2070
2546
        :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
2071
2547
                extra computation.
 
2548
 
 
2549
        If packed_stat and fingerprint are not given, they're invalidated in
 
2550
        the entry.
2072
2551
        """
2073
2552
        block = self._find_block(key)[1]
2074
2553
        if packed_stat is None:
2075
2554
            packed_stat = DirState.NULLSTAT
 
2555
        # XXX: Some callers pass '' as the packed_stat, and it seems to be
 
2556
        # sometimes present in the dirstate - this seems oddly inconsistent.
 
2557
        # mbp 20071008
2076
2558
        entry_index, present = self._find_entry_index(key, block)
2077
2559
        new_details = (minikind, fingerprint, size, executable, packed_stat)
2078
2560
        id_index = self._get_id_index()
2094
2576
                    # the test for existing kinds is different: this can be
2095
2577
                    # factored out to a helper though.
2096
2578
                    other_block_index, present = self._find_block_index_from_key(other_key)
2097
 
                    assert present, 'could not find block for %s' % (other_key,)
 
2579
                    if not present:
 
2580
                        raise AssertionError('could not find block for %s' % (other_key,))
2098
2581
                    other_entry_index, present = self._find_entry_index(other_key,
2099
2582
                                            self._dirblocks[other_block_index][1])
2100
 
                    assert present, 'could not find entry for %s' % (other_key,)
2101
 
                    assert path_utf8 is not None
 
2583
                    if not present:
 
2584
                        raise AssertionError('could not find entry for %s' % (other_key,))
 
2585
                    if path_utf8 is None:
 
2586
                        raise AssertionError('no path')
2102
2587
                    self._dirblocks[other_block_index][1][other_entry_index][1][0] = \
2103
2588
                        ('r', path_utf8, 0, False, '')
2104
2589
 
2105
2590
                num_present_parents = self._num_present_parents()
2106
2591
                for lookup_index in xrange(1, num_present_parents + 1):
2107
2592
                    # grab any one entry, use it to find the right path.
2108
 
                    # TODO: optimise this to reduce memory use in highly 
 
2593
                    # TODO: optimise this to reduce memory use in highly
2109
2594
                    # fragmented situations by reusing the relocation
2110
2595
                    # records.
2111
2596
                    update_block_index, present = \
2112
2597
                        self._find_block_index_from_key(other_key)
2113
 
                    assert present, 'could not find block for %s' % (other_key,)
 
2598
                    if not present:
 
2599
                        raise AssertionError('could not find block for %s' % (other_key,))
2114
2600
                    update_entry_index, present = \
2115
2601
                        self._find_entry_index(other_key, self._dirblocks[update_block_index][1])
2116
 
                    assert present, 'could not find entry for %s' % (other_key,)
 
2602
                    if not present:
 
2603
                        raise AssertionError('could not find entry for %s' % (other_key,))
2117
2604
                    update_details = self._dirblocks[update_block_index][1][update_entry_index][1][lookup_index]
2118
 
                    if update_details[0] in ('r', 'a'): # relocated, absent
 
2605
                    if update_details[0] in 'ar': # relocated, absent
2119
2606
                        # its a pointer or absent in lookup_index's tree, use
2120
2607
                        # it as is.
2121
2608
                        new_entry[1].append(update_details)
2126
2613
            block.insert(entry_index, new_entry)
2127
2614
            existing_keys.add(key)
2128
2615
        else:
2129
 
            # Does the new state matter? 
 
2616
            # Does the new state matter?
2130
2617
            block[entry_index][1][0] = new_details
2131
2618
            # parents cannot be affected by what we do.
2132
 
            # other occurences of this id can be found 
 
2619
            # other occurences of this id can be found
2133
2620
            # from the id index.
2134
2621
            # ---
2135
2622
            # tree index consistency: All other paths for this id in this tree
2137
2624
            # we may have passed entries in the state with this file id already
2138
2625
            # that were absent - where parent entries are - and they need to be
2139
2626
            # converted to relocated.
2140
 
            assert path_utf8 is not None
 
2627
            if path_utf8 is None:
 
2628
                raise AssertionError('no path')
2141
2629
            for entry_key in id_index.setdefault(key[2], set()):
2142
2630
                # TODO:PROFILING: It might be faster to just update
2143
2631
                # rather than checking if we need to, and then overwrite
2148
2636
                    # This is the vertical axis in the matrix, all pointing
2149
2637
                    # to the real path.
2150
2638
                    block_index, present = self._find_block_index_from_key(entry_key)
2151
 
                    assert present
 
2639
                    if not present:
 
2640
                        raise AssertionError('not present: %r', entry_key)
2152
2641
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
2153
 
                    assert present
 
2642
                    if not present:
 
2643
                        raise AssertionError('not present: %r', entry_key)
2154
2644
                    self._dirblocks[block_index][1][entry_index][1][0] = \
2155
2645
                        ('r', path_utf8, 0, False, '')
2156
2646
        # add a containing dirblock if needed.
2165
2655
    def _validate(self):
2166
2656
        """Check that invariants on the dirblock are correct.
2167
2657
 
2168
 
        This can be useful in debugging; it shouldn't be necessary in 
 
2658
        This can be useful in debugging; it shouldn't be necessary in
2169
2659
        normal code.
2170
2660
 
2171
2661
        This must be called with a lock held.
2187
2677
            if not self._dirblocks[0][0] == '':
2188
2678
                raise AssertionError(
2189
2679
                    "dirblocks don't start with root block:\n" + \
2190
 
                    pformat(dirblocks))
 
2680
                    pformat(self._dirblocks))
2191
2681
        if len(self._dirblocks) > 1:
2192
2682
            if not self._dirblocks[1][0] == '':
2193
2683
                raise AssertionError(
2194
2684
                    "dirblocks missing root directory:\n" + \
2195
 
                    pformat(dirblocks))
 
2685
                    pformat(self._dirblocks))
2196
2686
        # the dirblocks are sorted by their path components, name, and dir id
2197
2687
        dir_names = [d[0].split('/')
2198
2688
                for d in self._dirblocks[1:]]
2216
2706
                    "dirblock for %r is not sorted:\n%s" % \
2217
2707
                    (dirblock[0], pformat(dirblock)))
2218
2708
 
 
2709
        def check_valid_parent():
 
2710
            """Check that the current entry has a valid parent.
 
2711
 
 
2712
            This makes sure that the parent has a record,
 
2713
            and that the parent isn't marked as "absent" in the
 
2714
            current tree. (It is invalid to have a non-absent file in an absent
 
2715
            directory.)
 
2716
            """
 
2717
            if entry[0][0:2] == ('', ''):
 
2718
                # There should be no parent for the root row
 
2719
                return
 
2720
            parent_entry = self._get_entry(tree_index, path_utf8=entry[0][0])
 
2721
            if parent_entry == (None, None):
 
2722
                raise AssertionError(
 
2723
                    "no parent entry for: %s in tree %s"
 
2724
                    % (this_path, tree_index))
 
2725
            if parent_entry[1][tree_index][0] != 'd':
 
2726
                raise AssertionError(
 
2727
                    "Parent entry for %s is not marked as a valid"
 
2728
                    " directory. %s" % (this_path, parent_entry,))
 
2729
 
2219
2730
        # For each file id, for each tree: either
2220
2731
        # the file id is not present at all; all rows with that id in the
2221
2732
        # key have it marked as 'absent'
2222
 
        # OR the file id is present under exactly one name; any other entries 
 
2733
        # OR the file id is present under exactly one name; any other entries
2223
2734
        # that mention that id point to the correct name.
2224
2735
        #
2225
2736
        # We check this with a dict per tree pointing either to the present
2235
2746
                "wrong number of entry details for row\n%s" \
2236
2747
                ",\nexpected %d" % \
2237
2748
                (pformat(entry), tree_count))
 
2749
            absent_positions = 0
2238
2750
            for tree_index, tree_state in enumerate(entry[1]):
2239
2751
                this_tree_map = id_path_maps[tree_index]
2240
2752
                minikind = tree_state[0]
 
2753
                if minikind in 'ar':
 
2754
                    absent_positions += 1
2241
2755
                # have we seen this id before in this column?
2242
2756
                if file_id in this_tree_map:
2243
 
                    previous_path = this_tree_map[file_id]
 
2757
                    previous_path, previous_loc = this_tree_map[file_id]
2244
2758
                    # any later mention of this file must be consistent with
2245
2759
                    # what was said before
2246
2760
                    if minikind == 'a':
2260
2774
                        # pointed to by a relocation, which must point here
2261
2775
                        if previous_path != this_path:
2262
2776
                            raise AssertionError(
2263
 
                            "entry %r inconsistent with previous path %r" % \
2264
 
                            (entry, previous_path))
 
2777
                                "entry %r inconsistent with previous path %r "
 
2778
                                "seen at %r" %
 
2779
                                (entry, previous_path, previous_loc))
 
2780
                        check_valid_parent()
2265
2781
                else:
2266
2782
                    if minikind == 'a':
2267
2783
                        # absent; should not occur anywhere else
2268
 
                        this_tree_map[file_id] = None
 
2784
                        this_tree_map[file_id] = None, this_path
2269
2785
                    elif minikind == 'r':
2270
 
                        # relocation, must occur at expected location 
2271
 
                        this_tree_map[file_id] = tree_state[1]
 
2786
                        # relocation, must occur at expected location
 
2787
                        this_tree_map[file_id] = tree_state[1], this_path
2272
2788
                    else:
2273
 
                        this_tree_map[file_id] = this_path
 
2789
                        this_tree_map[file_id] = this_path, this_path
 
2790
                        check_valid_parent()
 
2791
            if absent_positions == tree_count:
 
2792
                raise AssertionError(
 
2793
                    "entry %r has no data for any tree." % (entry,))
2274
2794
 
2275
2795
    def _wipe_state(self):
2276
2796
        """Forget all state information about the dirstate."""
2277
2797
        self._header_state = DirState.NOT_IN_MEMORY
2278
2798
        self._dirblock_state = DirState.NOT_IN_MEMORY
 
2799
        self._changes_aborted = False
2279
2800
        self._parents = []
2280
2801
        self._ghosts = []
2281
2802
        self._dirblocks = []
2282
2803
        self._id_index = None
 
2804
        self._packed_stat_index = None
2283
2805
        self._end_of_header = None
2284
2806
        self._cutoff_time = None
2285
2807
        self._split_path_cache = {}
2286
2808
 
2287
2809
    def lock_read(self):
2288
 
        """Acquire a read lock on the dirstate"""
 
2810
        """Acquire a read lock on the dirstate."""
2289
2811
        if self._lock_token is not None:
2290
2812
            raise errors.LockContention(self._lock_token)
2291
2813
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2298
2820
        self._wipe_state()
2299
2821
 
2300
2822
    def lock_write(self):
2301
 
        """Acquire a write lock on the dirstate"""
 
2823
        """Acquire a write lock on the dirstate."""
2302
2824
        if self._lock_token is not None:
2303
2825
            raise errors.LockContention(self._lock_token)
2304
2826
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2311
2833
        self._wipe_state()
2312
2834
 
2313
2835
    def unlock(self):
2314
 
        """Drop any locks held on the dirstate"""
 
2836
        """Drop any locks held on the dirstate."""
2315
2837
        if self._lock_token is None:
2316
2838
            raise errors.LockNotHeld(self)
2317
2839
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2325
2847
        self._split_path_cache = {}
2326
2848
 
2327
2849
    def _requires_lock(self):
2328
 
        """Checks that a lock is currently held by someone on the dirstate"""
 
2850
        """Check that a lock is currently held by someone on the dirstate."""
2329
2851
        if not self._lock_token:
2330
2852
            raise errors.ObjectNotLocked(self)
2331
2853
 
2332
2854
 
2333
 
def bisect_dirblock(dirblocks, dirname, lo=0, hi=None, cache={}):
2334
 
    """Return the index where to insert dirname into the dirblocks.
2335
 
 
2336
 
    The return value idx is such that all directories blocks in dirblock[:idx]
2337
 
    have names < dirname, and all blocks in dirblock[idx:] have names >=
2338
 
    dirname.
2339
 
 
2340
 
    Optional args lo (default 0) and hi (default len(dirblocks)) bound the
2341
 
    slice of a to be searched.
 
2855
def py_update_entry(state, entry, abspath, stat_value,
 
2856
                 _stat_to_minikind=DirState._stat_to_minikind,
 
2857
                 _pack_stat=pack_stat):
 
2858
    """Update the entry based on what is actually on disk.
 
2859
 
 
2860
    This function only calculates the sha if it needs to - if the entry is
 
2861
    uncachable, or clearly different to the first parent's entry, no sha
 
2862
    is calculated, and None is returned.
 
2863
 
 
2864
    :param state: The dirstate this entry is in.
 
2865
    :param entry: This is the dirblock entry for the file in question.
 
2866
    :param abspath: The path on disk for this file.
 
2867
    :param stat_value: The stat value done on the path.
 
2868
    :return: None, or The sha1 hexdigest of the file (40 bytes) or link
 
2869
        target of a symlink.
2342
2870
    """
2343
 
    if hi is None:
2344
 
        hi = len(dirblocks)
2345
2871
    try:
2346
 
        dirname_split = cache[dirname]
 
2872
        minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
2347
2873
    except KeyError:
2348
 
        dirname_split = dirname.split('/')
2349
 
        cache[dirname] = dirname_split
2350
 
    while lo < hi:
2351
 
        mid = (lo+hi)//2
2352
 
        # Grab the dirname for the current dirblock
2353
 
        cur = dirblocks[mid][0]
2354
 
        try:
2355
 
            cur_split = cache[cur]
2356
 
        except KeyError:
2357
 
            cur_split = cur.split('/')
2358
 
            cache[cur] = cur_split
2359
 
        if cur_split < dirname_split: lo = mid+1
2360
 
        else: hi = mid
2361
 
    return lo
2362
 
 
2363
 
 
2364
 
 
2365
 
def pack_stat(st, _encode=base64.encodestring, _pack=struct.pack):
2366
 
    """Convert stat values into a packed representation."""
2367
 
    # jam 20060614 it isn't really worth removing more entries if we
2368
 
    # are going to leave it in packed form.
2369
 
    # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
2370
 
    # With all entries filesize is 5.9M and read time is mabye 280ms
2371
 
    # well within the noise margin
2372
 
 
2373
 
    # base64.encode always adds a final newline, so strip it off
2374
 
    return _encode(_pack('>LLLLLL'
2375
 
        , st.st_size, int(st.st_mtime), int(st.st_ctime)
2376
 
        , st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
2874
        # Unhandled kind
 
2875
        return None
 
2876
    packed_stat = _pack_stat(stat_value)
 
2877
    (saved_minikind, saved_link_or_sha1, saved_file_size,
 
2878
     saved_executable, saved_packed_stat) = entry[1][0]
 
2879
 
 
2880
    if minikind == 'd' and saved_minikind == 't':
 
2881
        minikind = 't'
 
2882
    if (minikind == saved_minikind
 
2883
        and packed_stat == saved_packed_stat):
 
2884
        # The stat hasn't changed since we saved, so we can re-use the
 
2885
        # saved sha hash.
 
2886
        if minikind == 'd':
 
2887
            return None
 
2888
 
 
2889
        # size should also be in packed_stat
 
2890
        if saved_file_size == stat_value.st_size:
 
2891
            return saved_link_or_sha1
 
2892
 
 
2893
    # If we have gotten this far, that means that we need to actually
 
2894
    # process this entry.
 
2895
    link_or_sha1 = None
 
2896
    if minikind == 'f':
 
2897
        executable = state._is_executable(stat_value.st_mode,
 
2898
                                         saved_executable)
 
2899
        if state._cutoff_time is None:
 
2900
            state._sha_cutoff_time()
 
2901
        if (stat_value.st_mtime < state._cutoff_time
 
2902
            and stat_value.st_ctime < state._cutoff_time
 
2903
            and len(entry[1]) > 1
 
2904
            and entry[1][1][0] != 'a'):
 
2905
            # Could check for size changes for further optimised
 
2906
            # avoidance of sha1's. However the most prominent case of
 
2907
            # over-shaing is during initial add, which this catches.
 
2908
            # Besides, if content filtering happens, size and sha
 
2909
            # are calculated at the same time, so checking just the size
 
2910
            # gains nothing w.r.t. performance.
 
2911
            link_or_sha1 = state._sha1_file(abspath)
 
2912
            entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
 
2913
                           executable, packed_stat)
 
2914
        else:
 
2915
            entry[1][0] = ('f', '', stat_value.st_size,
 
2916
                           executable, DirState.NULLSTAT)
 
2917
    elif minikind == 'd':
 
2918
        link_or_sha1 = None
 
2919
        entry[1][0] = ('d', '', 0, False, packed_stat)
 
2920
        if saved_minikind != 'd':
 
2921
            # This changed from something into a directory. Make sure we
 
2922
            # have a directory block for it. This doesn't happen very
 
2923
            # often, so this doesn't have to be super fast.
 
2924
            block_index, entry_index, dir_present, file_present = \
 
2925
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
 
2926
            state._ensure_block(block_index, entry_index,
 
2927
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
2928
    elif minikind == 'l':
 
2929
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
 
2930
        if state._cutoff_time is None:
 
2931
            state._sha_cutoff_time()
 
2932
        if (stat_value.st_mtime < state._cutoff_time
 
2933
            and stat_value.st_ctime < state._cutoff_time):
 
2934
            entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
 
2935
                           False, packed_stat)
 
2936
        else:
 
2937
            entry[1][0] = ('l', '', stat_value.st_size,
 
2938
                           False, DirState.NULLSTAT)
 
2939
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2940
    return link_or_sha1
 
2941
update_entry = py_update_entry
 
2942
 
 
2943
 
 
2944
class ProcessEntryPython(object):
 
2945
 
 
2946
    __slots__ = ["old_dirname_to_file_id", "new_dirname_to_file_id", "uninteresting",
 
2947
        "last_source_parent", "last_target_parent", "include_unchanged",
 
2948
        "use_filesystem_for_exec", "utf8_decode", "searched_specific_files",
 
2949
        "search_specific_files", "state", "source_index", "target_index",
 
2950
        "want_unversioned", "tree"]
 
2951
 
 
2952
    def __init__(self, include_unchanged, use_filesystem_for_exec,
 
2953
        search_specific_files, state, source_index, target_index,
 
2954
        want_unversioned, tree):
 
2955
        self.old_dirname_to_file_id = {}
 
2956
        self.new_dirname_to_file_id = {}
 
2957
        # Just a sentry, so that _process_entry can say that this
 
2958
        # record is handled, but isn't interesting to process (unchanged)
 
2959
        self.uninteresting = object()
 
2960
        # Using a list so that we can access the values and change them in
 
2961
        # nested scope. Each one is [path, file_id, entry]
 
2962
        self.last_source_parent = [None, None]
 
2963
        self.last_target_parent = [None, None]
 
2964
        self.include_unchanged = include_unchanged
 
2965
        self.use_filesystem_for_exec = use_filesystem_for_exec
 
2966
        self.utf8_decode = cache_utf8._utf8_decode
 
2967
        # for all search_indexs in each path at or under each element of
 
2968
        # search_specific_files, if the detail is relocated: add the id, and add the
 
2969
        # relocated path as one to search if its not searched already. If the
 
2970
        # detail is not relocated, add the id.
 
2971
        self.searched_specific_files = set()
 
2972
        self.search_specific_files = search_specific_files
 
2973
        self.state = state
 
2974
        self.source_index = source_index
 
2975
        self.target_index = target_index
 
2976
        self.want_unversioned = want_unversioned
 
2977
        self.tree = tree
 
2978
 
 
2979
    def _process_entry(self, entry, path_info, pathjoin=osutils.pathjoin):
 
2980
        """Compare an entry and real disk to generate delta information.
 
2981
 
 
2982
        :param path_info: top_relpath, basename, kind, lstat, abspath for
 
2983
            the path of entry. If None, then the path is considered absent.
 
2984
            (Perhaps we should pass in a concrete entry for this ?)
 
2985
            Basename is returned as a utf8 string because we expect this
 
2986
            tuple will be ignored, and don't want to take the time to
 
2987
            decode.
 
2988
        :return: None if these don't match
 
2989
                 A tuple of information about the change, or
 
2990
                 the object 'uninteresting' if these match, but are
 
2991
                 basically identical.
 
2992
        """
 
2993
        if self.source_index is None:
 
2994
            source_details = DirState.NULL_PARENT_DETAILS
 
2995
        else:
 
2996
            source_details = entry[1][self.source_index]
 
2997
        target_details = entry[1][self.target_index]
 
2998
        target_minikind = target_details[0]
 
2999
        if path_info is not None and target_minikind in 'fdlt':
 
3000
            if not (self.target_index == 0):
 
3001
                raise AssertionError()
 
3002
            link_or_sha1 = update_entry(self.state, entry,
 
3003
                abspath=path_info[4], stat_value=path_info[3])
 
3004
            # The entry may have been modified by update_entry
 
3005
            target_details = entry[1][self.target_index]
 
3006
            target_minikind = target_details[0]
 
3007
        else:
 
3008
            link_or_sha1 = None
 
3009
        file_id = entry[0][2]
 
3010
        source_minikind = source_details[0]
 
3011
        if source_minikind in 'fdltr' and target_minikind in 'fdlt':
 
3012
            # claimed content in both: diff
 
3013
            #   r    | fdlt   |      | add source to search, add id path move and perform
 
3014
            #        |        |      | diff check on source-target
 
3015
            #   r    | fdlt   |  a   | dangling file that was present in the basis.
 
3016
            #        |        |      | ???
 
3017
            if source_minikind in 'r':
 
3018
                # add the source to the search path to find any children it
 
3019
                # has.  TODO ? : only add if it is a container ?
 
3020
                if not osutils.is_inside_any(self.searched_specific_files,
 
3021
                                             source_details[1]):
 
3022
                    self.search_specific_files.add(source_details[1])
 
3023
                # generate the old path; this is needed for stating later
 
3024
                # as well.
 
3025
                old_path = source_details[1]
 
3026
                old_dirname, old_basename = os.path.split(old_path)
 
3027
                path = pathjoin(entry[0][0], entry[0][1])
 
3028
                old_entry = self.state._get_entry(self.source_index,
 
3029
                                             path_utf8=old_path)
 
3030
                # update the source details variable to be the real
 
3031
                # location.
 
3032
                if old_entry == (None, None):
 
3033
                    raise errors.CorruptDirstate(self.state._filename,
 
3034
                        "entry '%s/%s' is considered renamed from %r"
 
3035
                        " but source does not exist\n"
 
3036
                        "entry: %s" % (entry[0][0], entry[0][1], old_path, entry))
 
3037
                source_details = old_entry[1][self.source_index]
 
3038
                source_minikind = source_details[0]
 
3039
            else:
 
3040
                old_dirname = entry[0][0]
 
3041
                old_basename = entry[0][1]
 
3042
                old_path = path = None
 
3043
            if path_info is None:
 
3044
                # the file is missing on disk, show as removed.
 
3045
                content_change = True
 
3046
                target_kind = None
 
3047
                target_exec = False
 
3048
            else:
 
3049
                # source and target are both versioned and disk file is present.
 
3050
                target_kind = path_info[2]
 
3051
                if target_kind == 'directory':
 
3052
                    if path is None:
 
3053
                        old_path = path = pathjoin(old_dirname, old_basename)
 
3054
                    self.new_dirname_to_file_id[path] = file_id
 
3055
                    if source_minikind != 'd':
 
3056
                        content_change = True
 
3057
                    else:
 
3058
                        # directories have no fingerprint
 
3059
                        content_change = False
 
3060
                    target_exec = False
 
3061
                elif target_kind == 'file':
 
3062
                    if source_minikind != 'f':
 
3063
                        content_change = True
 
3064
                    else:
 
3065
                        # If the size is the same, check the sha:
 
3066
                        if target_details[2] == source_details[2]:
 
3067
                            if link_or_sha1 is None:
 
3068
                                # Stat cache miss:
 
3069
                                statvalue, link_or_sha1 = \
 
3070
                                    self.state._sha1_provider.stat_and_sha1(
 
3071
                                    path_info[4])
 
3072
                                self.state._observed_sha1(entry, link_or_sha1,
 
3073
                                    statvalue)
 
3074
                            content_change = (link_or_sha1 != source_details[1])
 
3075
                        else:
 
3076
                            # Size changed, so must be different
 
3077
                            content_change = True
 
3078
                    # Target details is updated at update_entry time
 
3079
                    if self.use_filesystem_for_exec:
 
3080
                        # We don't need S_ISREG here, because we are sure
 
3081
                        # we are dealing with a file.
 
3082
                        target_exec = bool(stat.S_IEXEC & path_info[3].st_mode)
 
3083
                    else:
 
3084
                        target_exec = target_details[3]
 
3085
                elif target_kind == 'symlink':
 
3086
                    if source_minikind != 'l':
 
3087
                        content_change = True
 
3088
                    else:
 
3089
                        content_change = (link_or_sha1 != source_details[1])
 
3090
                    target_exec = False
 
3091
                elif target_kind == 'tree-reference':
 
3092
                    if source_minikind != 't':
 
3093
                        content_change = True
 
3094
                    else:
 
3095
                        content_change = False
 
3096
                    target_exec = False
 
3097
                else:
 
3098
                    raise Exception, "unknown kind %s" % path_info[2]
 
3099
            if source_minikind == 'd':
 
3100
                if path is None:
 
3101
                    old_path = path = pathjoin(old_dirname, old_basename)
 
3102
                self.old_dirname_to_file_id[old_path] = file_id
 
3103
            # parent id is the entry for the path in the target tree
 
3104
            if old_dirname == self.last_source_parent[0]:
 
3105
                source_parent_id = self.last_source_parent[1]
 
3106
            else:
 
3107
                try:
 
3108
                    source_parent_id = self.old_dirname_to_file_id[old_dirname]
 
3109
                except KeyError:
 
3110
                    source_parent_entry = self.state._get_entry(self.source_index,
 
3111
                                                           path_utf8=old_dirname)
 
3112
                    source_parent_id = source_parent_entry[0][2]
 
3113
                if source_parent_id == entry[0][2]:
 
3114
                    # This is the root, so the parent is None
 
3115
                    source_parent_id = None
 
3116
                else:
 
3117
                    self.last_source_parent[0] = old_dirname
 
3118
                    self.last_source_parent[1] = source_parent_id
 
3119
            new_dirname = entry[0][0]
 
3120
            if new_dirname == self.last_target_parent[0]:
 
3121
                target_parent_id = self.last_target_parent[1]
 
3122
            else:
 
3123
                try:
 
3124
                    target_parent_id = self.new_dirname_to_file_id[new_dirname]
 
3125
                except KeyError:
 
3126
                    # TODO: We don't always need to do the lookup, because the
 
3127
                    #       parent entry will be the same as the source entry.
 
3128
                    target_parent_entry = self.state._get_entry(self.target_index,
 
3129
                                                           path_utf8=new_dirname)
 
3130
                    if target_parent_entry == (None, None):
 
3131
                        raise AssertionError(
 
3132
                            "Could not find target parent in wt: %s\nparent of: %s"
 
3133
                            % (new_dirname, entry))
 
3134
                    target_parent_id = target_parent_entry[0][2]
 
3135
                if target_parent_id == entry[0][2]:
 
3136
                    # This is the root, so the parent is None
 
3137
                    target_parent_id = None
 
3138
                else:
 
3139
                    self.last_target_parent[0] = new_dirname
 
3140
                    self.last_target_parent[1] = target_parent_id
 
3141
 
 
3142
            source_exec = source_details[3]
 
3143
            if (self.include_unchanged
 
3144
                or content_change
 
3145
                or source_parent_id != target_parent_id
 
3146
                or old_basename != entry[0][1]
 
3147
                or source_exec != target_exec
 
3148
                ):
 
3149
                if old_path is None:
 
3150
                    old_path = path = pathjoin(old_dirname, old_basename)
 
3151
                    old_path_u = self.utf8_decode(old_path)[0]
 
3152
                    path_u = old_path_u
 
3153
                else:
 
3154
                    old_path_u = self.utf8_decode(old_path)[0]
 
3155
                    if old_path == path:
 
3156
                        path_u = old_path_u
 
3157
                    else:
 
3158
                        path_u = self.utf8_decode(path)[0]
 
3159
                source_kind = DirState._minikind_to_kind[source_minikind]
 
3160
                return (entry[0][2],
 
3161
                       (old_path_u, path_u),
 
3162
                       content_change,
 
3163
                       (True, True),
 
3164
                       (source_parent_id, target_parent_id),
 
3165
                       (self.utf8_decode(old_basename)[0], self.utf8_decode(entry[0][1])[0]),
 
3166
                       (source_kind, target_kind),
 
3167
                       (source_exec, target_exec))
 
3168
            else:
 
3169
                return self.uninteresting
 
3170
        elif source_minikind in 'a' and target_minikind in 'fdlt':
 
3171
            # looks like a new file
 
3172
            path = pathjoin(entry[0][0], entry[0][1])
 
3173
            # parent id is the entry for the path in the target tree
 
3174
            # TODO: these are the same for an entire directory: cache em.
 
3175
            parent_id = self.state._get_entry(self.target_index,
 
3176
                                         path_utf8=entry[0][0])[0][2]
 
3177
            if parent_id == entry[0][2]:
 
3178
                parent_id = None
 
3179
            if path_info is not None:
 
3180
                # Present on disk:
 
3181
                if self.use_filesystem_for_exec:
 
3182
                    # We need S_ISREG here, because we aren't sure if this
 
3183
                    # is a file or not.
 
3184
                    target_exec = bool(
 
3185
                        stat.S_ISREG(path_info[3].st_mode)
 
3186
                        and stat.S_IEXEC & path_info[3].st_mode)
 
3187
                else:
 
3188
                    target_exec = target_details[3]
 
3189
                return (entry[0][2],
 
3190
                       (None, self.utf8_decode(path)[0]),
 
3191
                       True,
 
3192
                       (False, True),
 
3193
                       (None, parent_id),
 
3194
                       (None, self.utf8_decode(entry[0][1])[0]),
 
3195
                       (None, path_info[2]),
 
3196
                       (None, target_exec))
 
3197
            else:
 
3198
                # Its a missing file, report it as such.
 
3199
                return (entry[0][2],
 
3200
                       (None, self.utf8_decode(path)[0]),
 
3201
                       False,
 
3202
                       (False, True),
 
3203
                       (None, parent_id),
 
3204
                       (None, self.utf8_decode(entry[0][1])[0]),
 
3205
                       (None, None),
 
3206
                       (None, False))
 
3207
        elif source_minikind in 'fdlt' and target_minikind in 'a':
 
3208
            # unversioned, possibly, or possibly not deleted: we dont care.
 
3209
            # if its still on disk, *and* theres no other entry at this
 
3210
            # path [we dont know this in this routine at the moment -
 
3211
            # perhaps we should change this - then it would be an unknown.
 
3212
            old_path = pathjoin(entry[0][0], entry[0][1])
 
3213
            # parent id is the entry for the path in the target tree
 
3214
            parent_id = self.state._get_entry(self.source_index, path_utf8=entry[0][0])[0][2]
 
3215
            if parent_id == entry[0][2]:
 
3216
                parent_id = None
 
3217
            return (entry[0][2],
 
3218
                   (self.utf8_decode(old_path)[0], None),
 
3219
                   True,
 
3220
                   (True, False),
 
3221
                   (parent_id, None),
 
3222
                   (self.utf8_decode(entry[0][1])[0], None),
 
3223
                   (DirState._minikind_to_kind[source_minikind], None),
 
3224
                   (source_details[3], None))
 
3225
        elif source_minikind in 'fdlt' and target_minikind in 'r':
 
3226
            # a rename; could be a true rename, or a rename inherited from
 
3227
            # a renamed parent. TODO: handle this efficiently. Its not
 
3228
            # common case to rename dirs though, so a correct but slow
 
3229
            # implementation will do.
 
3230
            if not osutils.is_inside_any(self.searched_specific_files, target_details[1]):
 
3231
                self.search_specific_files.add(target_details[1])
 
3232
        elif source_minikind in 'ra' and target_minikind in 'ra':
 
3233
            # neither of the selected trees contain this file,
 
3234
            # so skip over it. This is not currently directly tested, but
 
3235
            # is indirectly via test_too_much.TestCommands.test_conflicts.
 
3236
            pass
 
3237
        else:
 
3238
            raise AssertionError("don't know how to compare "
 
3239
                "source_minikind=%r, target_minikind=%r"
 
3240
                % (source_minikind, target_minikind))
 
3241
            ## import pdb;pdb.set_trace()
 
3242
        return None
 
3243
 
 
3244
    def __iter__(self):
 
3245
        return self
 
3246
 
 
3247
    def iter_changes(self):
 
3248
        """Iterate over the changes."""
 
3249
        utf8_decode = cache_utf8._utf8_decode
 
3250
        _cmp_by_dirs = cmp_by_dirs
 
3251
        _process_entry = self._process_entry
 
3252
        uninteresting = self.uninteresting
 
3253
        search_specific_files = self.search_specific_files
 
3254
        searched_specific_files = self.searched_specific_files
 
3255
        splitpath = osutils.splitpath
 
3256
        # sketch:
 
3257
        # compare source_index and target_index at or under each element of search_specific_files.
 
3258
        # follow the following comparison table. Note that we only want to do diff operations when
 
3259
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo
 
3260
        # for the target.
 
3261
        # cases:
 
3262
        #
 
3263
        # Source | Target | disk | action
 
3264
        #   r    | fdlt   |      | add source to search, add id path move and perform
 
3265
        #        |        |      | diff check on source-target
 
3266
        #   r    | fdlt   |  a   | dangling file that was present in the basis.
 
3267
        #        |        |      | ???
 
3268
        #   r    |  a     |      | add source to search
 
3269
        #   r    |  a     |  a   |
 
3270
        #   r    |  r     |      | this path is present in a non-examined tree, skip.
 
3271
        #   r    |  r     |  a   | this path is present in a non-examined tree, skip.
 
3272
        #   a    | fdlt   |      | add new id
 
3273
        #   a    | fdlt   |  a   | dangling locally added file, skip
 
3274
        #   a    |  a     |      | not present in either tree, skip
 
3275
        #   a    |  a     |  a   | not present in any tree, skip
 
3276
        #   a    |  r     |      | not present in either tree at this path, skip as it
 
3277
        #        |        |      | may not be selected by the users list of paths.
 
3278
        #   a    |  r     |  a   | not present in either tree at this path, skip as it
 
3279
        #        |        |      | may not be selected by the users list of paths.
 
3280
        #  fdlt  | fdlt   |      | content in both: diff them
 
3281
        #  fdlt  | fdlt   |  a   | deleted locally, but not unversioned - show as deleted ?
 
3282
        #  fdlt  |  a     |      | unversioned: output deleted id for now
 
3283
        #  fdlt  |  a     |  a   | unversioned and deleted: output deleted id
 
3284
        #  fdlt  |  r     |      | relocated in this tree, so add target to search.
 
3285
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
 
3286
        #        |        |      | this id at the other path.
 
3287
        #  fdlt  |  r     |  a   | relocated in this tree, so add target to search.
 
3288
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
 
3289
        #        |        |      | this id at the other path.
 
3290
 
 
3291
        # TODO: jam 20070516 - Avoid the _get_entry lookup overhead by
 
3292
        #       keeping a cache of directories that we have seen.
 
3293
 
 
3294
        while search_specific_files:
 
3295
            # TODO: the pending list should be lexically sorted?  the
 
3296
            # interface doesn't require it.
 
3297
            current_root = search_specific_files.pop()
 
3298
            current_root_unicode = current_root.decode('utf8')
 
3299
            searched_specific_files.add(current_root)
 
3300
            # process the entries for this containing directory: the rest will be
 
3301
            # found by their parents recursively.
 
3302
            root_entries = self.state._entries_for_path(current_root)
 
3303
            root_abspath = self.tree.abspath(current_root_unicode)
 
3304
            try:
 
3305
                root_stat = os.lstat(root_abspath)
 
3306
            except OSError, e:
 
3307
                if e.errno == errno.ENOENT:
 
3308
                    # the path does not exist: let _process_entry know that.
 
3309
                    root_dir_info = None
 
3310
                else:
 
3311
                    # some other random error: hand it up.
 
3312
                    raise
 
3313
            else:
 
3314
                root_dir_info = ('', current_root,
 
3315
                    osutils.file_kind_from_stat_mode(root_stat.st_mode), root_stat,
 
3316
                    root_abspath)
 
3317
                if root_dir_info[2] == 'directory':
 
3318
                    if self.tree._directory_is_tree_reference(
 
3319
                        current_root.decode('utf8')):
 
3320
                        root_dir_info = root_dir_info[:2] + \
 
3321
                            ('tree-reference',) + root_dir_info[3:]
 
3322
 
 
3323
            if not root_entries and not root_dir_info:
 
3324
                # this specified path is not present at all, skip it.
 
3325
                continue
 
3326
            path_handled = False
 
3327
            for entry in root_entries:
 
3328
                result = _process_entry(entry, root_dir_info)
 
3329
                if result is not None:
 
3330
                    path_handled = True
 
3331
                    if result is not uninteresting:
 
3332
                        yield result
 
3333
            if self.want_unversioned and not path_handled and root_dir_info:
 
3334
                new_executable = bool(
 
3335
                    stat.S_ISREG(root_dir_info[3].st_mode)
 
3336
                    and stat.S_IEXEC & root_dir_info[3].st_mode)
 
3337
                yield (None,
 
3338
                       (None, current_root_unicode),
 
3339
                       True,
 
3340
                       (False, False),
 
3341
                       (None, None),
 
3342
                       (None, splitpath(current_root_unicode)[-1]),
 
3343
                       (None, root_dir_info[2]),
 
3344
                       (None, new_executable)
 
3345
                      )
 
3346
            initial_key = (current_root, '', '')
 
3347
            block_index, _ = self.state._find_block_index_from_key(initial_key)
 
3348
            if block_index == 0:
 
3349
                # we have processed the total root already, but because the
 
3350
                # initial key matched it we should skip it here.
 
3351
                block_index +=1
 
3352
            if root_dir_info and root_dir_info[2] == 'tree-reference':
 
3353
                current_dir_info = None
 
3354
            else:
 
3355
                dir_iterator = osutils._walkdirs_utf8(root_abspath, prefix=current_root)
 
3356
                try:
 
3357
                    current_dir_info = dir_iterator.next()
 
3358
                except OSError, e:
 
3359
                    # on win32, python2.4 has e.errno == ERROR_DIRECTORY, but
 
3360
                    # python 2.5 has e.errno == EINVAL,
 
3361
                    #            and e.winerror == ERROR_DIRECTORY
 
3362
                    e_winerror = getattr(e, 'winerror', None)
 
3363
                    win_errors = (ERROR_DIRECTORY, ERROR_PATH_NOT_FOUND)
 
3364
                    # there may be directories in the inventory even though
 
3365
                    # this path is not a file on disk: so mark it as end of
 
3366
                    # iterator
 
3367
                    if e.errno in (errno.ENOENT, errno.ENOTDIR, errno.EINVAL):
 
3368
                        current_dir_info = None
 
3369
                    elif (sys.platform == 'win32'
 
3370
                          and (e.errno in win_errors
 
3371
                               or e_winerror in win_errors)):
 
3372
                        current_dir_info = None
 
3373
                    else:
 
3374
                        raise
 
3375
                else:
 
3376
                    if current_dir_info[0][0] == '':
 
3377
                        # remove .bzr from iteration
 
3378
                        bzr_index = bisect.bisect_left(current_dir_info[1], ('.bzr',))
 
3379
                        if current_dir_info[1][bzr_index][0] != '.bzr':
 
3380
                            raise AssertionError()
 
3381
                        del current_dir_info[1][bzr_index]
 
3382
            # walk until both the directory listing and the versioned metadata
 
3383
            # are exhausted.
 
3384
            if (block_index < len(self.state._dirblocks) and
 
3385
                osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
 
3386
                current_block = self.state._dirblocks[block_index]
 
3387
            else:
 
3388
                current_block = None
 
3389
            while (current_dir_info is not None or
 
3390
                   current_block is not None):
 
3391
                if (current_dir_info and current_block
 
3392
                    and current_dir_info[0][0] != current_block[0]):
 
3393
                    if _cmp_by_dirs(current_dir_info[0][0], current_block[0]) < 0:
 
3394
                        # filesystem data refers to paths not covered by the dirblock.
 
3395
                        # this has two possibilities:
 
3396
                        # A) it is versioned but empty, so there is no block for it
 
3397
                        # B) it is not versioned.
 
3398
 
 
3399
                        # if (A) then we need to recurse into it to check for
 
3400
                        # new unknown files or directories.
 
3401
                        # if (B) then we should ignore it, because we don't
 
3402
                        # recurse into unknown directories.
 
3403
                        path_index = 0
 
3404
                        while path_index < len(current_dir_info[1]):
 
3405
                                current_path_info = current_dir_info[1][path_index]
 
3406
                                if self.want_unversioned:
 
3407
                                    if current_path_info[2] == 'directory':
 
3408
                                        if self.tree._directory_is_tree_reference(
 
3409
                                            current_path_info[0].decode('utf8')):
 
3410
                                            current_path_info = current_path_info[:2] + \
 
3411
                                                ('tree-reference',) + current_path_info[3:]
 
3412
                                    new_executable = bool(
 
3413
                                        stat.S_ISREG(current_path_info[3].st_mode)
 
3414
                                        and stat.S_IEXEC & current_path_info[3].st_mode)
 
3415
                                    yield (None,
 
3416
                                        (None, utf8_decode(current_path_info[0])[0]),
 
3417
                                        True,
 
3418
                                        (False, False),
 
3419
                                        (None, None),
 
3420
                                        (None, utf8_decode(current_path_info[1])[0]),
 
3421
                                        (None, current_path_info[2]),
 
3422
                                        (None, new_executable))
 
3423
                                # dont descend into this unversioned path if it is
 
3424
                                # a dir
 
3425
                                if current_path_info[2] in ('directory',
 
3426
                                                            'tree-reference'):
 
3427
                                    del current_dir_info[1][path_index]
 
3428
                                    path_index -= 1
 
3429
                                path_index += 1
 
3430
 
 
3431
                        # This dir info has been handled, go to the next
 
3432
                        try:
 
3433
                            current_dir_info = dir_iterator.next()
 
3434
                        except StopIteration:
 
3435
                            current_dir_info = None
 
3436
                    else:
 
3437
                        # We have a dirblock entry for this location, but there
 
3438
                        # is no filesystem path for this. This is most likely
 
3439
                        # because a directory was removed from the disk.
 
3440
                        # We don't have to report the missing directory,
 
3441
                        # because that should have already been handled, but we
 
3442
                        # need to handle all of the files that are contained
 
3443
                        # within.
 
3444
                        for current_entry in current_block[1]:
 
3445
                            # entry referring to file not present on disk.
 
3446
                            # advance the entry only, after processing.
 
3447
                            result = _process_entry(current_entry, None)
 
3448
                            if result is not None:
 
3449
                                if result is not uninteresting:
 
3450
                                    yield result
 
3451
                        block_index +=1
 
3452
                        if (block_index < len(self.state._dirblocks) and
 
3453
                            osutils.is_inside(current_root,
 
3454
                                              self.state._dirblocks[block_index][0])):
 
3455
                            current_block = self.state._dirblocks[block_index]
 
3456
                        else:
 
3457
                            current_block = None
 
3458
                    continue
 
3459
                entry_index = 0
 
3460
                if current_block and entry_index < len(current_block[1]):
 
3461
                    current_entry = current_block[1][entry_index]
 
3462
                else:
 
3463
                    current_entry = None
 
3464
                advance_entry = True
 
3465
                path_index = 0
 
3466
                if current_dir_info and path_index < len(current_dir_info[1]):
 
3467
                    current_path_info = current_dir_info[1][path_index]
 
3468
                    if current_path_info[2] == 'directory':
 
3469
                        if self.tree._directory_is_tree_reference(
 
3470
                            current_path_info[0].decode('utf8')):
 
3471
                            current_path_info = current_path_info[:2] + \
 
3472
                                ('tree-reference',) + current_path_info[3:]
 
3473
                else:
 
3474
                    current_path_info = None
 
3475
                advance_path = True
 
3476
                path_handled = False
 
3477
                while (current_entry is not None or
 
3478
                    current_path_info is not None):
 
3479
                    if current_entry is None:
 
3480
                        # the check for path_handled when the path is advanced
 
3481
                        # will yield this path if needed.
 
3482
                        pass
 
3483
                    elif current_path_info is None:
 
3484
                        # no path is fine: the per entry code will handle it.
 
3485
                        result = _process_entry(current_entry, current_path_info)
 
3486
                        if result is not None:
 
3487
                            if result is not uninteresting:
 
3488
                                yield result
 
3489
                    elif (current_entry[0][1] != current_path_info[1]
 
3490
                          or current_entry[1][self.target_index][0] in 'ar'):
 
3491
                        # The current path on disk doesn't match the dirblock
 
3492
                        # record. Either the dirblock is marked as absent, or
 
3493
                        # the file on disk is not present at all in the
 
3494
                        # dirblock. Either way, report about the dirblock
 
3495
                        # entry, and let other code handle the filesystem one.
 
3496
 
 
3497
                        # Compare the basename for these files to determine
 
3498
                        # which comes first
 
3499
                        if current_path_info[1] < current_entry[0][1]:
 
3500
                            # extra file on disk: pass for now, but only
 
3501
                            # increment the path, not the entry
 
3502
                            advance_entry = False
 
3503
                        else:
 
3504
                            # entry referring to file not present on disk.
 
3505
                            # advance the entry only, after processing.
 
3506
                            result = _process_entry(current_entry, None)
 
3507
                            if result is not None:
 
3508
                                if result is not uninteresting:
 
3509
                                    yield result
 
3510
                            advance_path = False
 
3511
                    else:
 
3512
                        result = _process_entry(current_entry, current_path_info)
 
3513
                        if result is not None:
 
3514
                            path_handled = True
 
3515
                            if result is not uninteresting:
 
3516
                                yield result
 
3517
                    if advance_entry and current_entry is not None:
 
3518
                        entry_index += 1
 
3519
                        if entry_index < len(current_block[1]):
 
3520
                            current_entry = current_block[1][entry_index]
 
3521
                        else:
 
3522
                            current_entry = None
 
3523
                    else:
 
3524
                        advance_entry = True # reset the advance flaga
 
3525
                    if advance_path and current_path_info is not None:
 
3526
                        if not path_handled:
 
3527
                            # unversioned in all regards
 
3528
                            if self.want_unversioned:
 
3529
                                new_executable = bool(
 
3530
                                    stat.S_ISREG(current_path_info[3].st_mode)
 
3531
                                    and stat.S_IEXEC & current_path_info[3].st_mode)
 
3532
                                try:
 
3533
                                    relpath_unicode = utf8_decode(current_path_info[0])[0]
 
3534
                                except UnicodeDecodeError:
 
3535
                                    raise errors.BadFilenameEncoding(
 
3536
                                        current_path_info[0], osutils._fs_enc)
 
3537
                                yield (None,
 
3538
                                    (None, relpath_unicode),
 
3539
                                    True,
 
3540
                                    (False, False),
 
3541
                                    (None, None),
 
3542
                                    (None, utf8_decode(current_path_info[1])[0]),
 
3543
                                    (None, current_path_info[2]),
 
3544
                                    (None, new_executable))
 
3545
                            # dont descend into this unversioned path if it is
 
3546
                            # a dir
 
3547
                            if current_path_info[2] in ('directory'):
 
3548
                                del current_dir_info[1][path_index]
 
3549
                                path_index -= 1
 
3550
                        # dont descend the disk iterator into any tree
 
3551
                        # paths.
 
3552
                        if current_path_info[2] == 'tree-reference':
 
3553
                            del current_dir_info[1][path_index]
 
3554
                            path_index -= 1
 
3555
                        path_index += 1
 
3556
                        if path_index < len(current_dir_info[1]):
 
3557
                            current_path_info = current_dir_info[1][path_index]
 
3558
                            if current_path_info[2] == 'directory':
 
3559
                                if self.tree._directory_is_tree_reference(
 
3560
                                    current_path_info[0].decode('utf8')):
 
3561
                                    current_path_info = current_path_info[:2] + \
 
3562
                                        ('tree-reference',) + current_path_info[3:]
 
3563
                        else:
 
3564
                            current_path_info = None
 
3565
                        path_handled = False
 
3566
                    else:
 
3567
                        advance_path = True # reset the advance flagg.
 
3568
                if current_block is not None:
 
3569
                    block_index += 1
 
3570
                    if (block_index < len(self.state._dirblocks) and
 
3571
                        osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
 
3572
                        current_block = self.state._dirblocks[block_index]
 
3573
                    else:
 
3574
                        current_block = None
 
3575
                if current_dir_info is not None:
 
3576
                    try:
 
3577
                        current_dir_info = dir_iterator.next()
 
3578
                    except StopIteration:
 
3579
                        current_dir_info = None
 
3580
_process_entry = ProcessEntryPython
 
3581
 
 
3582
 
 
3583
# Try to load the compiled form if possible
 
3584
try:
 
3585
    from bzrlib._dirstate_helpers_c import (
 
3586
        _read_dirblocks_c as _read_dirblocks,
 
3587
        bisect_dirblock_c as bisect_dirblock,
 
3588
        _bisect_path_left_c as _bisect_path_left,
 
3589
        _bisect_path_right_c as _bisect_path_right,
 
3590
        cmp_by_dirs_c as cmp_by_dirs,
 
3591
        ProcessEntryC as _process_entry,
 
3592
        update_entry as update_entry,
 
3593
        )
 
3594
except ImportError:
 
3595
    from bzrlib._dirstate_helpers_py import (
 
3596
        _read_dirblocks_py as _read_dirblocks,
 
3597
        bisect_dirblock_py as bisect_dirblock,
 
3598
        _bisect_path_left_py as _bisect_path_left,
 
3599
        _bisect_path_right_py as _bisect_path_right,
 
3600
        cmp_by_dirs_py as cmp_by_dirs,
 
3601
        )