~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Martin Pool
  • Date: 2005-05-11 06:20:05 UTC
  • Revision ID: mbp@sourcefrog.net-20050511062005-297af3451635dae0
- Don't lose first line of command help!

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2010 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
"""DirState objects record the state of a directory and its bzr metadata.
18
 
 
19
 
Pseudo EBNF grammar for the state file. Fields are separated by NULLs, and
20
 
lines by NL. The field delimiters are ommitted in the grammar, line delimiters
21
 
are not - this is done for clarity of reading. All string data is in utf8.
22
 
 
23
 
MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
24
 
NL = "\n";
25
 
NULL = "\0";
26
 
WHOLE_NUMBER = {digit}, digit;
27
 
BOOLEAN = "y" | "n";
28
 
REVISION_ID = a non-empty utf8 string;
29
 
 
30
 
dirstate format = header line, full checksum, row count, parent details,
31
 
 ghost_details, entries;
32
 
header line = "#bazaar dirstate flat format 3", NL;
33
 
full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
34
 
row count = "num_entries: ", WHOLE_NUMBER, NL;
35
 
parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
36
 
ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
37
 
entries = {entry};
38
 
entry = entry_key, current_entry_details, {parent_entry_details};
39
 
entry_key = dirname,  basename, fileid;
40
 
current_entry_details = common_entry_details, working_entry_details;
41
 
parent_entry_details = common_entry_details, history_entry_details;
42
 
common_entry_details = MINIKIND, fingerprint, size, executable
43
 
working_entry_details = packed_stat
44
 
history_entry_details = REVISION_ID;
45
 
executable = BOOLEAN;
46
 
size = WHOLE_NUMBER;
47
 
fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
48
 
 
49
 
Given this definition, the following is useful to know:
50
 
entry (aka row) - all the data for a given key.
51
 
entry[0]: The key (dirname, basename, fileid)
52
 
entry[0][0]: dirname
53
 
entry[0][1]: basename
54
 
entry[0][2]: fileid
55
 
entry[1]: The tree(s) data for this path and id combination.
56
 
entry[1][0]: The current tree
57
 
entry[1][1]: The second tree
58
 
 
59
 
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate:
60
 
entry[1][0][0]: minikind
61
 
entry[1][0][1]: fingerprint
62
 
entry[1][0][2]: size
63
 
entry[1][0][3]: executable
64
 
entry[1][0][4]: packed_stat
65
 
OR (for non tree-0)
66
 
entry[1][1][4]: revision_id
67
 
 
68
 
There may be multiple rows at the root, one per id present in the root, so the
69
 
in memory root row is now:
70
 
self._dirblocks[0] -> ('', [entry ...]),
71
 
and the entries in there are
72
 
entries[0][0]: ''
73
 
entries[0][1]: ''
74
 
entries[0][2]: file_id
75
 
entries[1][0]: The tree data for the current tree for this fileid at /
76
 
etc.
77
 
 
78
 
Kinds:
79
 
'r' is a relocated entry: This path is not present in this tree with this id,
80
 
    but the id can be found at another location. The fingerprint is used to
81
 
    point to the target location.
82
 
'a' is an absent entry: In that tree the id is not present at this path.
83
 
'd' is a directory entry: This path in this tree is a directory with the
84
 
    current file id. There is no fingerprint for directories.
85
 
'f' is a file entry: As for directory, but it's a file. The fingerprint is the
86
 
    sha1 value of the file's canonical form, i.e. after any read filters have
87
 
    been applied to the convenience form stored in the working tree.
88
 
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
89
 
    link target.
90
 
't' is a reference to a nested subtree; the fingerprint is the referenced
91
 
    revision.
92
 
 
93
 
Ordering:
94
 
 
95
 
The entries on disk and in memory are ordered according to the following keys:
96
 
 
97
 
    directory, as a list of components
98
 
    filename
99
 
    file-id
100
 
 
101
 
--- Format 1 had the following different definition: ---
102
 
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
103
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
104
 
    {PARENT ROW}
105
 
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
106
 
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
107
 
    SHA1
108
 
 
109
 
PARENT ROW's are emitted for every parent that is not in the ghosts details
110
 
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
111
 
each row will have a PARENT ROW for foo and baz, but not for bar.
112
 
 
113
 
 
114
 
In any tree, a kind of 'moved' indicates that the fingerprint field
115
 
(which we treat as opaque data specific to the 'kind' anyway) has the
116
 
details for the id of this row in that tree.
117
 
 
118
 
I'm strongly tempted to add a id->path index as well, but I think that
119
 
where we need id->path mapping; we also usually read the whole file, so
120
 
I'm going to skip that for the moment, as we have the ability to locate
121
 
via bisect any path in any tree, and if we lookup things by path, we can
122
 
accumulate an id->path mapping as we go, which will tend to match what we
123
 
looked for.
124
 
 
125
 
I plan to implement this asap, so please speak up now to alter/tweak the
126
 
design - and once we stabilise on this, I'll update the wiki page for
127
 
it.
128
 
 
129
 
The rationale for all this is that we want fast operations for the
130
 
common case (diff/status/commit/merge on all files) and extremely fast
131
 
operations for the less common but still occurs a lot status/diff/commit
132
 
on specific files). Operations on specific files involve a scan for all
133
 
the children of a path, *in every involved tree*, which the current
134
 
format did not accommodate.
135
 
----
136
 
 
137
 
Design priorities:
138
 
 1) Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
139
 
 2) fall back current object model as needed.
140
 
 3) scale usably to the largest trees known today - say 50K entries. (mozilla
141
 
    is an example of this)
142
 
 
143
 
 
144
 
Locking:
145
 
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
146
 
 been modified, but will require that we flush/ignore cached stat-hit data
147
 
 because we won't want to restat all files on disk just because a lock was
148
 
 acquired, yet we cannot trust the data after the previous lock was released.
149
 
 
150
 
Memory representation:
151
 
 vector of all directories, and vector of the childen ?
152
 
   i.e.
153
 
     root_entrie = (direntry for root, [parent_direntries_for_root]),
154
 
     dirblocks = [
155
 
     ('', ['data for achild', 'data for bchild', 'data for cchild'])
156
 
     ('dir', ['achild', 'cchild', 'echild'])
157
 
     ]
158
 
    - single bisect to find N subtrees from a path spec
159
 
    - in-order for serialisation - this is 'dirblock' grouping.
160
 
    - insertion of a file '/a' affects only the '/' child-vector, that is, to
161
 
      insert 10K elements from scratch does not generates O(N^2) memoves of a
162
 
      single vector, rather each individual, which tends to be limited to a
163
 
      manageable number. Will scale badly on trees with 10K entries in a
164
 
      single directory. compare with Inventory.InventoryDirectory which has
165
 
      a dictionary for the children. No bisect capability, can only probe for
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.
170
 
open questions:
171
 
 
172
 
Maybe we should do a test profile of the core structure - 10K simulated
173
 
searches/lookups/etc?
174
 
 
175
 
Objects for each row?
176
 
The lifetime of Dirstate objects is current per lock, but see above for
177
 
possible extensions. The lifetime of a row from a dirstate is expected to be
178
 
very short in the optimistic case: which we are optimising for. For instance,
179
 
subtree status will determine from analysis of the disk data what rows need to
180
 
be examined at all, and will be able to determine from a single row whether
181
 
that file has altered or not, so we are aiming to process tens of thousands of
182
 
entries each second within the dirstate context, before exposing anything to
183
 
the larger codebase. This suggests we want the time for a single file
184
 
comparison to be < 0.1 milliseconds. That would give us 10000 paths per second
185
 
processed, and to scale to 100 thousand we'll another order of magnitude to do
186
 
that. Now, as the lifetime for all unchanged entries is the time to parse, stat
187
 
the file on disk, and then immediately discard, the overhead of object creation
188
 
becomes a significant cost.
189
 
 
190
 
Figures: Creating a tuple from 3 elements was profiled at 0.0625
191
 
microseconds, whereas creating a object which is subclassed from tuple was
192
 
0.500 microseconds, and creating an object with 3 elements and slots was 3
193
 
microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get
194
 
down to 10 microseconds for the total processing - having 33% of that be object
195
 
creation is a huge overhead. There is a potential cost in using tuples within
196
 
each row which is that the conditional code to do comparisons may be slower
197
 
than method invocation, but method invocation is known to be slow due to stack
198
 
frame creation, so avoiding methods in these tight inner loops in unfortunately
199
 
desirable. We can consider a pyrex version of this with objects in future if
200
 
desired.
201
 
 
202
 
"""
203
 
 
204
 
import bisect
205
 
import binascii
206
 
import errno
207
 
import operator
208
 
import os
209
 
from stat import S_IEXEC
210
 
import stat
211
 
import struct
212
 
import sys
213
 
import time
214
 
import zlib
215
 
 
216
 
from bzrlib import (
217
 
    cache_utf8,
218
 
    debug,
219
 
    errors,
220
 
    inventory,
221
 
    lock,
222
 
    osutils,
223
 
    trace,
224
 
    )
225
 
 
226
 
 
227
 
# This is the Windows equivalent of ENOTDIR
228
 
# It is defined in pywin32.winerror, but we don't want a strong dependency for
229
 
# just an error code.
230
 
ERROR_PATH_NOT_FOUND = 3
231
 
ERROR_DIRECTORY = 267
232
 
 
233
 
 
234
 
if not getattr(struct, '_compile', None):
235
 
    # Cannot pre-compile the dirstate pack_stat
236
 
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
237
 
        """Convert stat values into a packed representation."""
238
 
        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),
239
 
            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,
240
 
            st.st_mode))[:-1]
241
 
else:
242
 
    # compile the struct compiler we need, so as to only do it once
243
 
    from _struct import Struct
244
 
    _compiled_pack = Struct('>LLLLLL').pack
245
 
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):
246
 
        """Convert stat values into a packed representation."""
247
 
        # jam 20060614 it isn't really worth removing more entries if we
248
 
        # are going to leave it in packed form.
249
 
        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
250
 
        # With all entries, filesize is 5.9M and read time is maybe 280ms
251
 
        # well within the noise margin
252
 
 
253
 
        # base64 encoding always adds a final newline, so strip it off
254
 
        # The current version
255
 
        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),
256
 
            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
257
 
        # This is 0.060s / 1.520s faster by not encoding as much information
258
 
        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
259
 
        # This is not strictly faster than _encode(_pack())[:-1]
260
 
        # return '%X.%X.%X.%X.%X.%X' % (
261
 
        #      st.st_size, int(st.st_mtime), int(st.st_ctime),
262
 
        #      st.st_dev, st.st_ino, st.st_mode)
263
 
        # Similar to the _encode(_pack('>LL'))
264
 
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
265
 
 
266
 
 
267
 
class SHA1Provider(object):
268
 
    """An interface for getting sha1s of a file."""
269
 
 
270
 
    def sha1(self, abspath):
271
 
        """Return the sha1 of a file given its absolute path.
272
 
 
273
 
        :param abspath:  May be a filesystem encoded absolute path
274
 
             or a unicode path.
275
 
        """
276
 
        raise NotImplementedError(self.sha1)
277
 
 
278
 
    def stat_and_sha1(self, abspath):
279
 
        """Return the stat and sha1 of a file given its absolute path.
280
 
        
281
 
        :param abspath:  May be a filesystem encoded absolute path
282
 
             or a unicode path.
283
 
 
284
 
        Note: the stat should be the stat of the physical file
285
 
        while the sha may be the sha of its canonical content.
286
 
        """
287
 
        raise NotImplementedError(self.stat_and_sha1)
288
 
 
289
 
 
290
 
class DefaultSHA1Provider(SHA1Provider):
291
 
    """A SHA1Provider that reads directly from the filesystem."""
292
 
 
293
 
    def sha1(self, abspath):
294
 
        """Return the sha1 of a file given its absolute path."""
295
 
        return osutils.sha_file_by_name(abspath)
296
 
 
297
 
    def stat_and_sha1(self, abspath):
298
 
        """Return the stat and sha1 of a file given its absolute path."""
299
 
        file_obj = file(abspath, 'rb')
300
 
        try:
301
 
            statvalue = os.fstat(file_obj.fileno())
302
 
            sha1 = osutils.sha_file(file_obj)
303
 
        finally:
304
 
            file_obj.close()
305
 
        return statvalue, sha1
306
 
 
307
 
 
308
 
class DirState(object):
309
 
    """Record directory and metadata state for fast access.
310
 
 
311
 
    A dirstate is a specialised data structure for managing local working
312
 
    tree state information. Its not yet well defined whether it is platform
313
 
    specific, and if it is how we detect/parameterize that.
314
 
 
315
 
    Dirstates use the usual lock_write, lock_read and unlock mechanisms.
316
 
    Unlike most bzr disk formats, DirStates must be locked for reading, using
317
 
    lock_read.  (This is an os file lock internally.)  This is necessary
318
 
    because the file can be rewritten in place.
319
 
 
320
 
    DirStates must be explicitly written with save() to commit changes; just
321
 
    unlocking them does not write the changes to disk.
322
 
    """
323
 
 
324
 
    _kind_to_minikind = {
325
 
            'absent': 'a',
326
 
            'file': 'f',
327
 
            'directory': 'd',
328
 
            'relocated': 'r',
329
 
            'symlink': 'l',
330
 
            'tree-reference': 't',
331
 
        }
332
 
    _minikind_to_kind = {
333
 
            'a': 'absent',
334
 
            'f': 'file',
335
 
            'd': 'directory',
336
 
            'l':'symlink',
337
 
            'r': 'relocated',
338
 
            't': 'tree-reference',
339
 
        }
340
 
    _stat_to_minikind = {
341
 
        stat.S_IFDIR:'d',
342
 
        stat.S_IFREG:'f',
343
 
        stat.S_IFLNK:'l',
344
 
    }
345
 
    _to_yesno = {True:'y', False: 'n'} # TODO profile the performance gain
346
 
     # of using int conversion rather than a dict here. AND BLAME ANDREW IF
347
 
     # it is faster.
348
 
 
349
 
    # TODO: jam 20070221 Figure out what to do if we have a record that exceeds
350
 
    #       the BISECT_PAGE_SIZE. For now, we just have to make it large enough
351
 
    #       that we are sure a single record will always fit.
352
 
    BISECT_PAGE_SIZE = 4096
353
 
 
354
 
    NOT_IN_MEMORY = 0
355
 
    IN_MEMORY_UNMODIFIED = 1
356
 
    IN_MEMORY_MODIFIED = 2
357
 
 
358
 
    # A pack_stat (the x's) that is just noise and will never match the output
359
 
    # of base64 encode.
360
 
    NULLSTAT = 'x' * 32
361
 
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
362
 
 
363
 
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
364
 
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
365
 
 
366
 
    def __init__(self, path, sha1_provider):
367
 
        """Create a  DirState object.
368
 
 
369
 
        :param path: The path at which the dirstate file on disk should live.
370
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
371
 
        """
372
 
        # _header_state and _dirblock_state represent the current state
373
 
        # of the dirstate metadata and the per-row data respectiely.
374
 
        # NOT_IN_MEMORY indicates that no data is in memory
375
 
        # IN_MEMORY_UNMODIFIED indicates that what we have in memory
376
 
        #   is the same as is on disk
377
 
        # IN_MEMORY_MODIFIED indicates that we have a modified version
378
 
        #   of what is on disk.
379
 
        # In future we will add more granularity, for instance _dirblock_state
380
 
        # will probably support partially-in-memory as a separate variable,
381
 
        # allowing for partially-in-memory unmodified and partially-in-memory
382
 
        # modified states.
383
 
        self._header_state = DirState.NOT_IN_MEMORY
384
 
        self._dirblock_state = DirState.NOT_IN_MEMORY
385
 
        # If true, an error has been detected while updating the dirstate, and
386
 
        # for safety we're not going to commit to disk.
387
 
        self._changes_aborted = False
388
 
        self._dirblocks = []
389
 
        self._ghosts = []
390
 
        self._parents = []
391
 
        self._state_file = None
392
 
        self._filename = path
393
 
        self._lock_token = None
394
 
        self._lock_state = None
395
 
        self._id_index = None
396
 
        # a map from packed_stat to sha's.
397
 
        self._packed_stat_index = None
398
 
        self._end_of_header = None
399
 
        self._cutoff_time = None
400
 
        self._split_path_cache = {}
401
 
        self._bisect_page_size = DirState.BISECT_PAGE_SIZE
402
 
        self._sha1_provider = sha1_provider
403
 
        if 'hashcache' in debug.debug_flags:
404
 
            self._sha1_file = self._sha1_file_and_mutter
405
 
        else:
406
 
            self._sha1_file = self._sha1_provider.sha1
407
 
        # These two attributes provide a simple cache for lookups into the
408
 
        # dirstate in-memory vectors. By probing respectively for the last
409
 
        # block, and for the next entry, we save nearly 2 bisections per path
410
 
        # during commit.
411
 
        self._last_block_index = None
412
 
        self._last_entry_index = None
413
 
 
414
 
    def __repr__(self):
415
 
        return "%s(%r)" % \
416
 
            (self.__class__.__name__, self._filename)
417
 
 
418
 
    def add(self, path, file_id, kind, stat, fingerprint):
419
 
        """Add a path to be tracked.
420
 
 
421
 
        :param path: The path within the dirstate - '' is the root, 'foo' is the
422
 
            path foo within the root, 'foo/bar' is the path bar within foo
423
 
            within the root.
424
 
        :param file_id: The file id of the path being added.
425
 
        :param kind: The kind of the path, as a string like 'file',
426
 
            'directory', etc.
427
 
        :param stat: The output of os.lstat for the path.
428
 
        :param fingerprint: The sha value of the file's canonical form (i.e.
429
 
            after any read filters have been applied),
430
 
            or the target of a symlink,
431
 
            or the referenced revision id for tree-references,
432
 
            or '' for directories.
433
 
        """
434
 
        # adding a file:
435
 
        # find the block its in.
436
 
        # find the location in the block.
437
 
        # check its not there
438
 
        # add it.
439
 
        #------- copied from inventory.ensure_normalized_name - keep synced.
440
 
        # --- normalized_filename wants a unicode basename only, so get one.
441
 
        dirname, basename = osutils.split(path)
442
 
        # we dont import normalized_filename directly because we want to be
443
 
        # able to change the implementation at runtime for tests.
444
 
        norm_name, can_access = osutils.normalized_filename(basename)
445
 
        if norm_name != basename:
446
 
            if can_access:
447
 
                basename = norm_name
448
 
            else:
449
 
                raise errors.InvalidNormalization(path)
450
 
        # you should never have files called . or ..; just add the directory
451
 
        # in the parent, or according to the special treatment for the root
452
 
        if basename == '.' or basename == '..':
453
 
            raise errors.InvalidEntryName(path)
454
 
        # now that we've normalised, we need the correct utf8 path and
455
 
        # dirname and basename elements. This single encode and split should be
456
 
        # faster than three separate encodes.
457
 
        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
458
 
        dirname, basename = osutils.split(utf8path)
459
 
        # uses __class__ for speed; the check is needed for safety
460
 
        if file_id.__class__ is not str:
461
 
            raise AssertionError(
462
 
                "must be a utf8 file_id not %s" % (type(file_id), ))
463
 
        # Make sure the file_id does not exist in this tree
464
 
        rename_from = None
465
 
        file_id_entry = self._get_entry(0, fileid_utf8=file_id, include_deleted=True)
466
 
        if file_id_entry != (None, None):
467
 
            if file_id_entry[1][0][0] == 'a':
468
 
                if file_id_entry[0] != (dirname, basename, file_id):
469
 
                    # set the old name's current operation to rename
470
 
                    self.update_minimal(file_id_entry[0],
471
 
                        'r',
472
 
                        path_utf8='',
473
 
                        packed_stat='',
474
 
                        fingerprint=utf8path
475
 
                    )
476
 
                    rename_from = file_id_entry[0][0:2]
477
 
            else:
478
 
                path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
479
 
                kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
480
 
                info = '%s:%s' % (kind, path)
481
 
                raise errors.DuplicateFileId(file_id, info)
482
 
        first_key = (dirname, basename, '')
483
 
        block_index, present = self._find_block_index_from_key(first_key)
484
 
        if present:
485
 
            # check the path is not in the tree
486
 
            block = self._dirblocks[block_index][1]
487
 
            entry_index, _ = self._find_entry_index(first_key, block)
488
 
            while (entry_index < len(block) and
489
 
                block[entry_index][0][0:2] == first_key[0:2]):
490
 
                if block[entry_index][1][0][0] not in 'ar':
491
 
                    # this path is in the dirstate in the current tree.
492
 
                    raise Exception, "adding already added path!"
493
 
                entry_index += 1
494
 
        else:
495
 
            # The block where we want to put the file is not present. But it
496
 
            # might be because the directory was empty, or not loaded yet. Look
497
 
            # for a parent entry, if not found, raise NotVersionedError
498
 
            parent_dir, parent_base = osutils.split(dirname)
499
 
            parent_block_idx, parent_entry_idx, _, parent_present = \
500
 
                self._get_block_entry_index(parent_dir, parent_base, 0)
501
 
            if not parent_present:
502
 
                raise errors.NotVersionedError(path, str(self))
503
 
            self._ensure_block(parent_block_idx, parent_entry_idx, dirname)
504
 
        block = self._dirblocks[block_index][1]
505
 
        entry_key = (dirname, basename, file_id)
506
 
        if stat is None:
507
 
            size = 0
508
 
            packed_stat = DirState.NULLSTAT
509
 
        else:
510
 
            size = stat.st_size
511
 
            packed_stat = pack_stat(stat)
512
 
        parent_info = self._empty_parent_info()
513
 
        minikind = DirState._kind_to_minikind[kind]
514
 
        if rename_from is not None:
515
 
            if rename_from[0]:
516
 
                old_path_utf8 = '%s/%s' % rename_from
517
 
            else:
518
 
                old_path_utf8 = rename_from[1]
519
 
            parent_info[0] = ('r', old_path_utf8, 0, False, '')
520
 
        if kind == 'file':
521
 
            entry_data = entry_key, [
522
 
                (minikind, fingerprint, size, False, packed_stat),
523
 
                ] + parent_info
524
 
        elif kind == 'directory':
525
 
            entry_data = entry_key, [
526
 
                (minikind, '', 0, False, packed_stat),
527
 
                ] + parent_info
528
 
        elif kind == 'symlink':
529
 
            entry_data = entry_key, [
530
 
                (minikind, fingerprint, size, False, packed_stat),
531
 
                ] + parent_info
532
 
        elif kind == 'tree-reference':
533
 
            entry_data = entry_key, [
534
 
                (minikind, fingerprint, 0, False, packed_stat),
535
 
                ] + parent_info
536
 
        else:
537
 
            raise errors.BzrError('unknown kind %r' % kind)
538
 
        entry_index, present = self._find_entry_index(entry_key, block)
539
 
        if not present:
540
 
            block.insert(entry_index, entry_data)
541
 
        else:
542
 
            if block[entry_index][1][0][0] != 'a':
543
 
                raise AssertionError(" %r(%r) already added" % (basename, file_id))
544
 
            block[entry_index][1][0] = entry_data[1][0]
545
 
 
546
 
        if kind == 'directory':
547
 
           # insert a new dirblock
548
 
           self._ensure_block(block_index, entry_index, utf8path)
549
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
550
 
        if self._id_index:
551
 
            self._id_index.setdefault(entry_key[2], set()).add(entry_key)
552
 
 
553
 
    def _bisect(self, paths):
554
 
        """Bisect through the disk structure for specific rows.
555
 
 
556
 
        :param paths: A list of paths to find
557
 
        :return: A dict mapping path => entries for found entries. Missing
558
 
                 entries will not be in the map.
559
 
                 The list is not sorted, and entries will be populated
560
 
                 based on when they were read.
561
 
        """
562
 
        self._requires_lock()
563
 
        # We need the file pointer to be right after the initial header block
564
 
        self._read_header_if_needed()
565
 
        # If _dirblock_state was in memory, we should just return info from
566
 
        # there, this function is only meant to handle when we want to read
567
 
        # part of the disk.
568
 
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
569
 
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
570
 
 
571
 
        # The disk representation is generally info + '\0\n\0' at the end. But
572
 
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
573
 
        # Because it means we can sync on the '\n'
574
 
        state_file = self._state_file
575
 
        file_size = os.fstat(state_file.fileno()).st_size
576
 
        # We end up with 2 extra fields, we should have a trailing '\n' to
577
 
        # ensure that we read the whole record, and we should have a precursur
578
 
        # '' which ensures that we start after the previous '\n'
579
 
        entry_field_count = self._fields_per_entry() + 1
580
 
 
581
 
        low = self._end_of_header
582
 
        high = file_size - 1 # Ignore the final '\0'
583
 
        # Map from (dir, name) => entry
584
 
        found = {}
585
 
 
586
 
        # Avoid infinite seeking
587
 
        max_count = 30*len(paths)
588
 
        count = 0
589
 
        # pending is a list of places to look.
590
 
        # each entry is a tuple of low, high, dir_names
591
 
        #   low -> the first byte offset to read (inclusive)
592
 
        #   high -> the last byte offset (inclusive)
593
 
        #   dir_names -> The list of (dir, name) pairs that should be found in
594
 
        #                the [low, high] range
595
 
        pending = [(low, high, paths)]
596
 
 
597
 
        page_size = self._bisect_page_size
598
 
 
599
 
        fields_to_entry = self._get_fields_to_entry()
600
 
 
601
 
        while pending:
602
 
            low, high, cur_files = pending.pop()
603
 
 
604
 
            if not cur_files or low >= high:
605
 
                # Nothing to find
606
 
                continue
607
 
 
608
 
            count += 1
609
 
            if count > max_count:
610
 
                raise errors.BzrError('Too many seeks, most likely a bug.')
611
 
 
612
 
            mid = max(low, (low+high-page_size)/2)
613
 
 
614
 
            state_file.seek(mid)
615
 
            # limit the read size, so we don't end up reading data that we have
616
 
            # already read.
617
 
            read_size = min(page_size, (high-mid)+1)
618
 
            block = state_file.read(read_size)
619
 
 
620
 
            start = mid
621
 
            entries = block.split('\n')
622
 
 
623
 
            if len(entries) < 2:
624
 
                # We didn't find a '\n', so we cannot have found any records.
625
 
                # So put this range back and try again. But we know we have to
626
 
                # increase the page size, because a single read did not contain
627
 
                # a record break (so records must be larger than page_size)
628
 
                page_size *= 2
629
 
                pending.append((low, high, cur_files))
630
 
                continue
631
 
 
632
 
            # Check the first and last entries, in case they are partial, or if
633
 
            # we don't care about the rest of this page
634
 
            first_entry_num = 0
635
 
            first_fields = entries[0].split('\0')
636
 
            if len(first_fields) < entry_field_count:
637
 
                # We didn't get the complete first entry
638
 
                # so move start, and grab the next, which
639
 
                # should be a full entry
640
 
                start += len(entries[0])+1
641
 
                first_fields = entries[1].split('\0')
642
 
                first_entry_num = 1
643
 
 
644
 
            if len(first_fields) <= 2:
645
 
                # We didn't even get a filename here... what do we do?
646
 
                # Try a large page size and repeat this query
647
 
                page_size *= 2
648
 
                pending.append((low, high, cur_files))
649
 
                continue
650
 
            else:
651
 
                # Find what entries we are looking for, which occur before and
652
 
                # after this first record.
653
 
                after = start
654
 
                if first_fields[1]:
655
 
                    first_path = first_fields[1] + '/' + first_fields[2]
656
 
                else:
657
 
                    first_path = first_fields[2]
658
 
                first_loc = _bisect_path_left(cur_files, first_path)
659
 
 
660
 
                # These exist before the current location
661
 
                pre = cur_files[:first_loc]
662
 
                # These occur after the current location, which may be in the
663
 
                # data we read, or might be after the last entry
664
 
                post = cur_files[first_loc:]
665
 
 
666
 
            if post and len(first_fields) >= entry_field_count:
667
 
                # We have files after the first entry
668
 
 
669
 
                # Parse the last entry
670
 
                last_entry_num = len(entries)-1
671
 
                last_fields = entries[last_entry_num].split('\0')
672
 
                if len(last_fields) < entry_field_count:
673
 
                    # The very last hunk was not complete,
674
 
                    # read the previous hunk
675
 
                    after = mid + len(block) - len(entries[-1])
676
 
                    last_entry_num -= 1
677
 
                    last_fields = entries[last_entry_num].split('\0')
678
 
                else:
679
 
                    after = mid + len(block)
680
 
 
681
 
                if last_fields[1]:
682
 
                    last_path = last_fields[1] + '/' + last_fields[2]
683
 
                else:
684
 
                    last_path = last_fields[2]
685
 
                last_loc = _bisect_path_right(post, last_path)
686
 
 
687
 
                middle_files = post[:last_loc]
688
 
                post = post[last_loc:]
689
 
 
690
 
                if middle_files:
691
 
                    # We have files that should occur in this block
692
 
                    # (>= first, <= last)
693
 
                    # Either we will find them here, or we can mark them as
694
 
                    # missing.
695
 
 
696
 
                    if middle_files[0] == first_path:
697
 
                        # We might need to go before this location
698
 
                        pre.append(first_path)
699
 
                    if middle_files[-1] == last_path:
700
 
                        post.insert(0, last_path)
701
 
 
702
 
                    # Find out what paths we have
703
 
                    paths = {first_path:[first_fields]}
704
 
                    # last_path might == first_path so we need to be
705
 
                    # careful if we should append rather than overwrite
706
 
                    if last_entry_num != first_entry_num:
707
 
                        paths.setdefault(last_path, []).append(last_fields)
708
 
                    for num in xrange(first_entry_num+1, last_entry_num):
709
 
                        # TODO: jam 20070223 We are already splitting here, so
710
 
                        #       shouldn't we just split the whole thing rather
711
 
                        #       than doing the split again in add_one_record?
712
 
                        fields = entries[num].split('\0')
713
 
                        if fields[1]:
714
 
                            path = fields[1] + '/' + fields[2]
715
 
                        else:
716
 
                            path = fields[2]
717
 
                        paths.setdefault(path, []).append(fields)
718
 
 
719
 
                    for path in middle_files:
720
 
                        for fields in paths.get(path, []):
721
 
                            # offset by 1 because of the opening '\0'
722
 
                            # consider changing fields_to_entry to avoid the
723
 
                            # extra list slice
724
 
                            entry = fields_to_entry(fields[1:])
725
 
                            found.setdefault(path, []).append(entry)
726
 
 
727
 
            # Now we have split up everything into pre, middle, and post, and
728
 
            # we have handled everything that fell in 'middle'.
729
 
            # We add 'post' first, so that we prefer to seek towards the
730
 
            # beginning, so that we will tend to go as early as we need, and
731
 
            # then only seek forward after that.
732
 
            if post:
733
 
                pending.append((after, high, post))
734
 
            if pre:
735
 
                pending.append((low, start-1, pre))
736
 
 
737
 
        # Consider that we may want to return the directory entries in sorted
738
 
        # order. For now, we just return them in whatever order we found them,
739
 
        # and leave it up to the caller if they care if it is ordered or not.
740
 
        return found
741
 
 
742
 
    def _bisect_dirblocks(self, dir_list):
743
 
        """Bisect through the disk structure to find entries in given dirs.
744
 
 
745
 
        _bisect_dirblocks is meant to find the contents of directories, which
746
 
        differs from _bisect, which only finds individual entries.
747
 
 
748
 
        :param dir_list: A sorted list of directory names ['', 'dir', 'foo'].
749
 
        :return: A map from dir => entries_for_dir
750
 
        """
751
 
        # TODO: jam 20070223 A lot of the bisecting logic could be shared
752
 
        #       between this and _bisect. It would require parameterizing the
753
 
        #       inner loop with a function, though. We should evaluate the
754
 
        #       performance difference.
755
 
        self._requires_lock()
756
 
        # We need the file pointer to be right after the initial header block
757
 
        self._read_header_if_needed()
758
 
        # If _dirblock_state was in memory, we should just return info from
759
 
        # there, this function is only meant to handle when we want to read
760
 
        # part of the disk.
761
 
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
762
 
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
763
 
        # The disk representation is generally info + '\0\n\0' at the end. But
764
 
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
765
 
        # Because it means we can sync on the '\n'
766
 
        state_file = self._state_file
767
 
        file_size = os.fstat(state_file.fileno()).st_size
768
 
        # We end up with 2 extra fields, we should have a trailing '\n' to
769
 
        # ensure that we read the whole record, and we should have a precursur
770
 
        # '' which ensures that we start after the previous '\n'
771
 
        entry_field_count = self._fields_per_entry() + 1
772
 
 
773
 
        low = self._end_of_header
774
 
        high = file_size - 1 # Ignore the final '\0'
775
 
        # Map from dir => entry
776
 
        found = {}
777
 
 
778
 
        # Avoid infinite seeking
779
 
        max_count = 30*len(dir_list)
780
 
        count = 0
781
 
        # pending is a list of places to look.
782
 
        # each entry is a tuple of low, high, dir_names
783
 
        #   low -> the first byte offset to read (inclusive)
784
 
        #   high -> the last byte offset (inclusive)
785
 
        #   dirs -> The list of directories that should be found in
786
 
        #                the [low, high] range
787
 
        pending = [(low, high, dir_list)]
788
 
 
789
 
        page_size = self._bisect_page_size
790
 
 
791
 
        fields_to_entry = self._get_fields_to_entry()
792
 
 
793
 
        while pending:
794
 
            low, high, cur_dirs = pending.pop()
795
 
 
796
 
            if not cur_dirs or low >= high:
797
 
                # Nothing to find
798
 
                continue
799
 
 
800
 
            count += 1
801
 
            if count > max_count:
802
 
                raise errors.BzrError('Too many seeks, most likely a bug.')
803
 
 
804
 
            mid = max(low, (low+high-page_size)/2)
805
 
 
806
 
            state_file.seek(mid)
807
 
            # limit the read size, so we don't end up reading data that we have
808
 
            # already read.
809
 
            read_size = min(page_size, (high-mid)+1)
810
 
            block = state_file.read(read_size)
811
 
 
812
 
            start = mid
813
 
            entries = block.split('\n')
814
 
 
815
 
            if len(entries) < 2:
816
 
                # We didn't find a '\n', so we cannot have found any records.
817
 
                # So put this range back and try again. But we know we have to
818
 
                # increase the page size, because a single read did not contain
819
 
                # a record break (so records must be larger than page_size)
820
 
                page_size *= 2
821
 
                pending.append((low, high, cur_dirs))
822
 
                continue
823
 
 
824
 
            # Check the first and last entries, in case they are partial, or if
825
 
            # we don't care about the rest of this page
826
 
            first_entry_num = 0
827
 
            first_fields = entries[0].split('\0')
828
 
            if len(first_fields) < entry_field_count:
829
 
                # We didn't get the complete first entry
830
 
                # so move start, and grab the next, which
831
 
                # should be a full entry
832
 
                start += len(entries[0])+1
833
 
                first_fields = entries[1].split('\0')
834
 
                first_entry_num = 1
835
 
 
836
 
            if len(first_fields) <= 1:
837
 
                # We didn't even get a dirname here... what do we do?
838
 
                # Try a large page size and repeat this query
839
 
                page_size *= 2
840
 
                pending.append((low, high, cur_dirs))
841
 
                continue
842
 
            else:
843
 
                # Find what entries we are looking for, which occur before and
844
 
                # after this first record.
845
 
                after = start
846
 
                first_dir = first_fields[1]
847
 
                first_loc = bisect.bisect_left(cur_dirs, first_dir)
848
 
 
849
 
                # These exist before the current location
850
 
                pre = cur_dirs[:first_loc]
851
 
                # These occur after the current location, which may be in the
852
 
                # data we read, or might be after the last entry
853
 
                post = cur_dirs[first_loc:]
854
 
 
855
 
            if post and len(first_fields) >= entry_field_count:
856
 
                # We have records to look at after the first entry
857
 
 
858
 
                # Parse the last entry
859
 
                last_entry_num = len(entries)-1
860
 
                last_fields = entries[last_entry_num].split('\0')
861
 
                if len(last_fields) < entry_field_count:
862
 
                    # The very last hunk was not complete,
863
 
                    # read the previous hunk
864
 
                    after = mid + len(block) - len(entries[-1])
865
 
                    last_entry_num -= 1
866
 
                    last_fields = entries[last_entry_num].split('\0')
867
 
                else:
868
 
                    after = mid + len(block)
869
 
 
870
 
                last_dir = last_fields[1]
871
 
                last_loc = bisect.bisect_right(post, last_dir)
872
 
 
873
 
                middle_files = post[:last_loc]
874
 
                post = post[last_loc:]
875
 
 
876
 
                if middle_files:
877
 
                    # We have files that should occur in this block
878
 
                    # (>= first, <= last)
879
 
                    # Either we will find them here, or we can mark them as
880
 
                    # missing.
881
 
 
882
 
                    if middle_files[0] == first_dir:
883
 
                        # We might need to go before this location
884
 
                        pre.append(first_dir)
885
 
                    if middle_files[-1] == last_dir:
886
 
                        post.insert(0, last_dir)
887
 
 
888
 
                    # Find out what paths we have
889
 
                    paths = {first_dir:[first_fields]}
890
 
                    # last_dir might == first_dir so we need to be
891
 
                    # careful if we should append rather than overwrite
892
 
                    if last_entry_num != first_entry_num:
893
 
                        paths.setdefault(last_dir, []).append(last_fields)
894
 
                    for num in xrange(first_entry_num+1, last_entry_num):
895
 
                        # TODO: jam 20070223 We are already splitting here, so
896
 
                        #       shouldn't we just split the whole thing rather
897
 
                        #       than doing the split again in add_one_record?
898
 
                        fields = entries[num].split('\0')
899
 
                        paths.setdefault(fields[1], []).append(fields)
900
 
 
901
 
                    for cur_dir in middle_files:
902
 
                        for fields in paths.get(cur_dir, []):
903
 
                            # offset by 1 because of the opening '\0'
904
 
                            # consider changing fields_to_entry to avoid the
905
 
                            # extra list slice
906
 
                            entry = fields_to_entry(fields[1:])
907
 
                            found.setdefault(cur_dir, []).append(entry)
908
 
 
909
 
            # Now we have split up everything into pre, middle, and post, and
910
 
            # we have handled everything that fell in 'middle'.
911
 
            # We add 'post' first, so that we prefer to seek towards the
912
 
            # beginning, so that we will tend to go as early as we need, and
913
 
            # then only seek forward after that.
914
 
            if post:
915
 
                pending.append((after, high, post))
916
 
            if pre:
917
 
                pending.append((low, start-1, pre))
918
 
 
919
 
        return found
920
 
 
921
 
    def _bisect_recursive(self, paths):
922
 
        """Bisect for entries for all paths and their children.
923
 
 
924
 
        This will use bisect to find all records for the supplied paths. It
925
 
        will then continue to bisect for any records which are marked as
926
 
        directories. (and renames?)
927
 
 
928
 
        :param paths: A sorted list of (dir, name) pairs
929
 
             eg: [('', 'a'), ('', 'f'), ('a/b', 'c')]
930
 
        :return: A dictionary mapping (dir, name, file_id) => [tree_info]
931
 
        """
932
 
        # Map from (dir, name, file_id) => [tree_info]
933
 
        found = {}
934
 
 
935
 
        found_dir_names = set()
936
 
 
937
 
        # Directories that have been read
938
 
        processed_dirs = set()
939
 
        # Get the ball rolling with the first bisect for all entries.
940
 
        newly_found = self._bisect(paths)
941
 
 
942
 
        while newly_found:
943
 
            # Directories that need to be read
944
 
            pending_dirs = set()
945
 
            paths_to_search = set()
946
 
            for entry_list in newly_found.itervalues():
947
 
                for dir_name_id, trees_info in entry_list:
948
 
                    found[dir_name_id] = trees_info
949
 
                    found_dir_names.add(dir_name_id[:2])
950
 
                    is_dir = False
951
 
                    for tree_info in trees_info:
952
 
                        minikind = tree_info[0]
953
 
                        if minikind == 'd':
954
 
                            if is_dir:
955
 
                                # We already processed this one as a directory,
956
 
                                # we don't need to do the extra work again.
957
 
                                continue
958
 
                            subdir, name, file_id = dir_name_id
959
 
                            path = osutils.pathjoin(subdir, name)
960
 
                            is_dir = True
961
 
                            if path not in processed_dirs:
962
 
                                pending_dirs.add(path)
963
 
                        elif minikind == 'r':
964
 
                            # Rename, we need to directly search the target
965
 
                            # which is contained in the fingerprint column
966
 
                            dir_name = osutils.split(tree_info[1])
967
 
                            if dir_name[0] in pending_dirs:
968
 
                                # This entry will be found in the dir search
969
 
                                continue
970
 
                            if dir_name not in found_dir_names:
971
 
                                paths_to_search.add(tree_info[1])
972
 
            # Now we have a list of paths to look for directly, and
973
 
            # directory blocks that need to be read.
974
 
            # newly_found is mixing the keys between (dir, name) and path
975
 
            # entries, but that is okay, because we only really care about the
976
 
            # targets.
977
 
            newly_found = self._bisect(sorted(paths_to_search))
978
 
            newly_found.update(self._bisect_dirblocks(sorted(pending_dirs)))
979
 
            processed_dirs.update(pending_dirs)
980
 
        return found
981
 
 
982
 
    def _discard_merge_parents(self):
983
 
        """Discard any parents trees beyond the first.
984
 
 
985
 
        Note that if this fails the dirstate is corrupted.
986
 
 
987
 
        After this function returns the dirstate contains 2 trees, neither of
988
 
        which are ghosted.
989
 
        """
990
 
        self._read_header_if_needed()
991
 
        parents = self.get_parent_ids()
992
 
        if len(parents) < 1:
993
 
            return
994
 
        # only require all dirblocks if we are doing a full-pass removal.
995
 
        self._read_dirblocks_if_needed()
996
 
        dead_patterns = set([('a', 'r'), ('a', 'a'), ('r', 'r'), ('r', 'a')])
997
 
        def iter_entries_removable():
998
 
            for block in self._dirblocks:
999
 
                deleted_positions = []
1000
 
                for pos, entry in enumerate(block[1]):
1001
 
                    yield entry
1002
 
                    if (entry[1][0][0], entry[1][1][0]) in dead_patterns:
1003
 
                        deleted_positions.append(pos)
1004
 
                if deleted_positions:
1005
 
                    if len(deleted_positions) == len(block[1]):
1006
 
                        del block[1][:]
1007
 
                    else:
1008
 
                        for pos in reversed(deleted_positions):
1009
 
                            del block[1][pos]
1010
 
        # if the first parent is a ghost:
1011
 
        if parents[0] in self.get_ghosts():
1012
 
            empty_parent = [DirState.NULL_PARENT_DETAILS]
1013
 
            for entry in iter_entries_removable():
1014
 
                entry[1][1:] = empty_parent
1015
 
        else:
1016
 
            for entry in iter_entries_removable():
1017
 
                del entry[1][2:]
1018
 
 
1019
 
        self._ghosts = []
1020
 
        self._parents = [parents[0]]
1021
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1022
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
1023
 
 
1024
 
    def _empty_parent_info(self):
1025
 
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1026
 
                                                    len(self._ghosts))
1027
 
 
1028
 
    def _ensure_block(self, parent_block_index, parent_row_index, dirname):
1029
 
        """Ensure a block for dirname exists.
1030
 
 
1031
 
        This function exists to let callers which know that there is a
1032
 
        directory dirname ensure that the block for it exists. This block can
1033
 
        fail to exist because of demand loading, or because a directory had no
1034
 
        children. In either case it is not an error. It is however an error to
1035
 
        call this if there is no parent entry for the directory, and thus the
1036
 
        function requires the coordinates of such an entry to be provided.
1037
 
 
1038
 
        The root row is special cased and can be indicated with a parent block
1039
 
        and row index of -1
1040
 
 
1041
 
        :param parent_block_index: The index of the block in which dirname's row
1042
 
            exists.
1043
 
        :param parent_row_index: The index in the parent block where the row
1044
 
            exists.
1045
 
        :param dirname: The utf8 dirname to ensure there is a block for.
1046
 
        :return: The index for the block.
1047
 
        """
1048
 
        if dirname == '' and parent_row_index == 0 and parent_block_index == 0:
1049
 
            # This is the signature of the root row, and the
1050
 
            # contents-of-root row is always index 1
1051
 
            return 1
1052
 
        # the basename of the directory must be the end of its full name.
1053
 
        if not (parent_block_index == -1 and
1054
 
            parent_block_index == -1 and dirname == ''):
1055
 
            if not dirname.endswith(
1056
 
                    self._dirblocks[parent_block_index][1][parent_row_index][0][1]):
1057
 
                raise AssertionError("bad dirname %r" % dirname)
1058
 
        block_index, present = self._find_block_index_from_key((dirname, '', ''))
1059
 
        if not present:
1060
 
            ## In future, when doing partial parsing, this should load and
1061
 
            # populate the entire block.
1062
 
            self._dirblocks.insert(block_index, (dirname, []))
1063
 
        return block_index
1064
 
 
1065
 
    def _entries_to_current_state(self, new_entries):
1066
 
        """Load new_entries into self.dirblocks.
1067
 
 
1068
 
        Process new_entries into the current state object, making them the active
1069
 
        state.  The entries are grouped together by directory to form dirblocks.
1070
 
 
1071
 
        :param new_entries: A sorted list of entries. This function does not sort
1072
 
            to prevent unneeded overhead when callers have a sorted list already.
1073
 
        :return: Nothing.
1074
 
        """
1075
 
        if new_entries[0][0][0:2] != ('', ''):
1076
 
            raise AssertionError(
1077
 
                "Missing root row %r" % (new_entries[0][0],))
1078
 
        # The two blocks here are deliberate: the root block and the
1079
 
        # contents-of-root block.
1080
 
        self._dirblocks = [('', []), ('', [])]
1081
 
        current_block = self._dirblocks[0][1]
1082
 
        current_dirname = ''
1083
 
        root_key = ('', '')
1084
 
        append_entry = current_block.append
1085
 
        for entry in new_entries:
1086
 
            if entry[0][0] != current_dirname:
1087
 
                # new block - different dirname
1088
 
                current_block = []
1089
 
                current_dirname = entry[0][0]
1090
 
                self._dirblocks.append((current_dirname, current_block))
1091
 
                append_entry = current_block.append
1092
 
            # append the entry to the current block
1093
 
            append_entry(entry)
1094
 
        self._split_root_dirblock_into_contents()
1095
 
 
1096
 
    def _split_root_dirblock_into_contents(self):
1097
 
        """Split the root dirblocks into root and contents-of-root.
1098
 
 
1099
 
        After parsing by path, we end up with root entries and contents-of-root
1100
 
        entries in the same block. This loop splits them out again.
1101
 
        """
1102
 
        # The above loop leaves the "root block" entries mixed with the
1103
 
        # "contents-of-root block". But we don't want an if check on
1104
 
        # all entries, so instead we just fix it up here.
1105
 
        if self._dirblocks[1] != ('', []):
1106
 
            raise ValueError("bad dirblock start %r" % (self._dirblocks[1],))
1107
 
        root_block = []
1108
 
        contents_of_root_block = []
1109
 
        for entry in self._dirblocks[0][1]:
1110
 
            if not entry[0][1]: # This is a root entry
1111
 
                root_block.append(entry)
1112
 
            else:
1113
 
                contents_of_root_block.append(entry)
1114
 
        self._dirblocks[0] = ('', root_block)
1115
 
        self._dirblocks[1] = ('', contents_of_root_block)
1116
 
 
1117
 
    def _entries_for_path(self, path):
1118
 
        """Return a list with all the entries that match path for all ids."""
1119
 
        dirname, basename = os.path.split(path)
1120
 
        key = (dirname, basename, '')
1121
 
        block_index, present = self._find_block_index_from_key(key)
1122
 
        if not present:
1123
 
            # the block which should contain path is absent.
1124
 
            return []
1125
 
        result = []
1126
 
        block = self._dirblocks[block_index][1]
1127
 
        entry_index, _ = self._find_entry_index(key, block)
1128
 
        # we may need to look at multiple entries at this path: walk while the specific_files match.
1129
 
        while (entry_index < len(block) and
1130
 
            block[entry_index][0][0:2] == key[0:2]):
1131
 
            result.append(block[entry_index])
1132
 
            entry_index += 1
1133
 
        return result
1134
 
 
1135
 
    def _entry_to_line(self, entry):
1136
 
        """Serialize entry to a NULL delimited line ready for _get_output_lines.
1137
 
 
1138
 
        :param entry: An entry_tuple as defined in the module docstring.
1139
 
        """
1140
 
        entire_entry = list(entry[0])
1141
 
        for tree_number, tree_data in enumerate(entry[1]):
1142
 
            # (minikind, fingerprint, size, executable, tree_specific_string)
1143
 
            entire_entry.extend(tree_data)
1144
 
            # 3 for the key, 5 for the fields per tree.
1145
 
            tree_offset = 3 + tree_number * 5
1146
 
            # minikind
1147
 
            entire_entry[tree_offset + 0] = tree_data[0]
1148
 
            # size
1149
 
            entire_entry[tree_offset + 2] = str(tree_data[2])
1150
 
            # executable
1151
 
            entire_entry[tree_offset + 3] = DirState._to_yesno[tree_data[3]]
1152
 
        return '\0'.join(entire_entry)
1153
 
 
1154
 
    def _fields_per_entry(self):
1155
 
        """How many null separated fields should be in each entry row.
1156
 
 
1157
 
        Each line now has an extra '\n' field which is not used
1158
 
        so we just skip over it
1159
 
        entry size:
1160
 
            3 fields for the key
1161
 
            + number of fields per tree_data (5) * tree count
1162
 
            + newline
1163
 
         """
1164
 
        tree_count = 1 + self._num_present_parents()
1165
 
        return 3 + 5 * tree_count + 1
1166
 
 
1167
 
    def _find_block(self, key, add_if_missing=False):
1168
 
        """Return the block that key should be present in.
1169
 
 
1170
 
        :param key: A dirstate entry key.
1171
 
        :return: The block tuple.
1172
 
        """
1173
 
        block_index, present = self._find_block_index_from_key(key)
1174
 
        if not present:
1175
 
            if not add_if_missing:
1176
 
                # check to see if key is versioned itself - we might want to
1177
 
                # add it anyway, because dirs with no entries dont get a
1178
 
                # dirblock at parse time.
1179
 
                # This is an uncommon branch to take: most dirs have children,
1180
 
                # and most code works with versioned paths.
1181
 
                parent_base, parent_name = osutils.split(key[0])
1182
 
                if not self._get_block_entry_index(parent_base, parent_name, 0)[3]:
1183
 
                    # some parent path has not been added - its an error to add
1184
 
                    # this child
1185
 
                    raise errors.NotVersionedError(key[0:2], str(self))
1186
 
            self._dirblocks.insert(block_index, (key[0], []))
1187
 
        return self._dirblocks[block_index]
1188
 
 
1189
 
    def _find_block_index_from_key(self, key):
1190
 
        """Find the dirblock index for a key.
1191
 
 
1192
 
        :return: The block index, True if the block for the key is present.
1193
 
        """
1194
 
        if key[0:2] == ('', ''):
1195
 
            return 0, True
1196
 
        try:
1197
 
            if (self._last_block_index is not None and
1198
 
                self._dirblocks[self._last_block_index][0] == key[0]):
1199
 
                return self._last_block_index, True
1200
 
        except IndexError:
1201
 
            pass
1202
 
        block_index = bisect_dirblock(self._dirblocks, key[0], 1,
1203
 
                                      cache=self._split_path_cache)
1204
 
        # _right returns one-past-where-key is so we have to subtract
1205
 
        # one to use it. we use _right here because there are two
1206
 
        # '' blocks - the root, and the contents of root
1207
 
        # we always have a minimum of 2 in self._dirblocks: root and
1208
 
        # root-contents, and for '', we get 2 back, so this is
1209
 
        # simple and correct:
1210
 
        present = (block_index < len(self._dirblocks) and
1211
 
            self._dirblocks[block_index][0] == key[0])
1212
 
        self._last_block_index = block_index
1213
 
        # Reset the entry index cache to the beginning of the block.
1214
 
        self._last_entry_index = -1
1215
 
        return block_index, present
1216
 
 
1217
 
    def _find_entry_index(self, key, block):
1218
 
        """Find the entry index for a key in a block.
1219
 
 
1220
 
        :return: The entry index, True if the entry for the key is present.
1221
 
        """
1222
 
        len_block = len(block)
1223
 
        try:
1224
 
            if self._last_entry_index is not None:
1225
 
                # mini-bisect here.
1226
 
                entry_index = self._last_entry_index + 1
1227
 
                # A hit is when the key is after the last slot, and before or
1228
 
                # equal to the next slot.
1229
 
                if ((entry_index > 0 and block[entry_index - 1][0] < key) and
1230
 
                    key <= block[entry_index][0]):
1231
 
                    self._last_entry_index = entry_index
1232
 
                    present = (block[entry_index][0] == key)
1233
 
                    return entry_index, present
1234
 
        except IndexError:
1235
 
            pass
1236
 
        entry_index = bisect.bisect_left(block, (key, []))
1237
 
        present = (entry_index < len_block and
1238
 
            block[entry_index][0] == key)
1239
 
        self._last_entry_index = entry_index
1240
 
        return entry_index, present
1241
 
 
1242
 
    @staticmethod
1243
 
    def from_tree(tree, dir_state_filename, sha1_provider=None):
1244
 
        """Create a dirstate from a bzr Tree.
1245
 
 
1246
 
        :param tree: The tree which should provide parent information and
1247
 
            inventory ids.
1248
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
1249
 
            If None, a DefaultSHA1Provider is used.
1250
 
        :return: a DirState object which is currently locked for writing.
1251
 
            (it was locked by DirState.initialize)
1252
 
        """
1253
 
        result = DirState.initialize(dir_state_filename,
1254
 
            sha1_provider=sha1_provider)
1255
 
        try:
1256
 
            tree.lock_read()
1257
 
            try:
1258
 
                parent_ids = tree.get_parent_ids()
1259
 
                num_parents = len(parent_ids)
1260
 
                parent_trees = []
1261
 
                for parent_id in parent_ids:
1262
 
                    parent_tree = tree.branch.repository.revision_tree(parent_id)
1263
 
                    parent_trees.append((parent_id, parent_tree))
1264
 
                    parent_tree.lock_read()
1265
 
                result.set_parent_trees(parent_trees, [])
1266
 
                result.set_state_from_inventory(tree.inventory)
1267
 
            finally:
1268
 
                for revid, parent_tree in parent_trees:
1269
 
                    parent_tree.unlock()
1270
 
                tree.unlock()
1271
 
        except:
1272
 
            # The caller won't have a chance to unlock this, so make sure we
1273
 
            # cleanup ourselves
1274
 
            result.unlock()
1275
 
            raise
1276
 
        return result
1277
 
 
1278
 
    def update_by_delta(self, delta):
1279
 
        """Apply an inventory delta to the dirstate for tree 0
1280
 
 
1281
 
        This is the workhorse for apply_inventory_delta in dirstate based
1282
 
        trees.
1283
 
 
1284
 
        :param delta: An inventory delta.  See Inventory.apply_delta for
1285
 
            details.
1286
 
        """
1287
 
        self._read_dirblocks_if_needed()
1288
 
        encode = cache_utf8.encode
1289
 
        insertions = {}
1290
 
        removals = {}
1291
 
        # Accumulate parent references (path_utf8, id), to check for parentless
1292
 
        # items or items placed under files/links/tree-references. We get
1293
 
        # references from every item in the delta that is not a deletion and
1294
 
        # is not itself the root.
1295
 
        parents = set()
1296
 
        # Added ids must not be in the dirstate already. This set holds those
1297
 
        # ids.
1298
 
        new_ids = set()
1299
 
        # This loop transforms the delta to single atomic operations that can
1300
 
        # be executed and validated.
1301
 
        for old_path, new_path, file_id, inv_entry in sorted(
1302
 
            inventory._check_delta_unique_old_paths(
1303
 
            inventory._check_delta_unique_new_paths(
1304
 
            inventory._check_delta_ids_match_entry(
1305
 
            inventory._check_delta_ids_are_valid(
1306
 
            inventory._check_delta_new_path_entry_both_or_None(delta))))),
1307
 
            reverse=True):
1308
 
            if (file_id in insertions) or (file_id in removals):
1309
 
                raise errors.InconsistentDelta(old_path or new_path, file_id,
1310
 
                    "repeated file_id")
1311
 
            if old_path is not None:
1312
 
                old_path = old_path.encode('utf-8')
1313
 
                removals[file_id] = old_path
1314
 
            else:
1315
 
                new_ids.add(file_id)
1316
 
            if new_path is not None:
1317
 
                if inv_entry is None:
1318
 
                    raise errors.InconsistentDelta(new_path, file_id,
1319
 
                        "new_path with no entry")
1320
 
                new_path = new_path.encode('utf-8')
1321
 
                dirname_utf8, basename = osutils.split(new_path)
1322
 
                if basename:
1323
 
                    parents.add((dirname_utf8, inv_entry.parent_id))
1324
 
                key = (dirname_utf8, basename, file_id)
1325
 
                minikind = DirState._kind_to_minikind[inv_entry.kind]
1326
 
                if minikind == 't':
1327
 
                    fingerprint = inv_entry.reference_revision or ''
1328
 
                else:
1329
 
                    fingerprint = ''
1330
 
                insertions[file_id] = (key, minikind, inv_entry.executable,
1331
 
                                       fingerprint, new_path)
1332
 
            # Transform moves into delete+add pairs
1333
 
            if None not in (old_path, new_path):
1334
 
                for child in self._iter_child_entries(0, old_path):
1335
 
                    if child[0][2] in insertions or child[0][2] in removals:
1336
 
                        continue
1337
 
                    child_dirname = child[0][0]
1338
 
                    child_basename = child[0][1]
1339
 
                    minikind = child[1][0][0]
1340
 
                    fingerprint = child[1][0][4]
1341
 
                    executable = child[1][0][3]
1342
 
                    old_child_path = osutils.pathjoin(child_dirname,
1343
 
                                                      child_basename)
1344
 
                    removals[child[0][2]] = old_child_path
1345
 
                    child_suffix = child_dirname[len(old_path):]
1346
 
                    new_child_dirname = (new_path + child_suffix)
1347
 
                    key = (new_child_dirname, child_basename, child[0][2])
1348
 
                    new_child_path = osutils.pathjoin(new_child_dirname,
1349
 
                                                      child_basename)
1350
 
                    insertions[child[0][2]] = (key, minikind, executable,
1351
 
                                               fingerprint, new_child_path)
1352
 
        self._check_delta_ids_absent(new_ids, delta, 0)
1353
 
        try:
1354
 
            self._apply_removals(removals.iteritems())
1355
 
            self._apply_insertions(insertions.values())
1356
 
            # Validate parents
1357
 
            self._after_delta_check_parents(parents, 0)
1358
 
        except errors.BzrError, e:
1359
 
            self._changes_aborted = True
1360
 
            if 'integrity error' not in str(e):
1361
 
                raise
1362
 
            # _get_entry raises BzrError when a request is inconsistent; we
1363
 
            # want such errors to be shown as InconsistentDelta - and that 
1364
 
            # fits the behaviour we trigger.
1365
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1366
 
 
1367
 
    def _apply_removals(self, removals):
1368
 
        for file_id, path in sorted(removals, reverse=True,
1369
 
            key=operator.itemgetter(1)):
1370
 
            dirname, basename = osutils.split(path)
1371
 
            block_i, entry_i, d_present, f_present = \
1372
 
                self._get_block_entry_index(dirname, basename, 0)
1373
 
            try:
1374
 
                entry = self._dirblocks[block_i][1][entry_i]
1375
 
            except IndexError:
1376
 
                self._changes_aborted = True
1377
 
                raise errors.InconsistentDelta(path, file_id,
1378
 
                    "Wrong path for old path.")
1379
 
            if not f_present or entry[1][0][0] in 'ar':
1380
 
                self._changes_aborted = True
1381
 
                raise errors.InconsistentDelta(path, file_id,
1382
 
                    "Wrong path for old path.")
1383
 
            if file_id != entry[0][2]:
1384
 
                self._changes_aborted = True
1385
 
                raise errors.InconsistentDelta(path, file_id,
1386
 
                    "Attempt to remove path has wrong id - found %r."
1387
 
                    % entry[0][2])
1388
 
            self._make_absent(entry)
1389
 
            # See if we have a malformed delta: deleting a directory must not
1390
 
            # leave crud behind. This increases the number of bisects needed
1391
 
            # substantially, but deletion or renames of large numbers of paths
1392
 
            # is rare enough it shouldn't be an issue (famous last words?) RBC
1393
 
            # 20080730.
1394
 
            block_i, entry_i, d_present, f_present = \
1395
 
                self._get_block_entry_index(path, '', 0)
1396
 
            if d_present:
1397
 
                # The dir block is still present in the dirstate; this could
1398
 
                # be due to it being in a parent tree, or a corrupt delta.
1399
 
                for child_entry in self._dirblocks[block_i][1]:
1400
 
                    if child_entry[1][0][0] not in ('r', 'a'):
1401
 
                        self._changes_aborted = True
1402
 
                        raise errors.InconsistentDelta(path, entry[0][2],
1403
 
                            "The file id was deleted but its children were "
1404
 
                            "not deleted.")
1405
 
 
1406
 
    def _apply_insertions(self, adds):
1407
 
        try:
1408
 
            for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
1409
 
                self.update_minimal(key, minikind, executable, fingerprint,
1410
 
                                    path_utf8=path_utf8)
1411
 
        except errors.NotVersionedError:
1412
 
            self._changes_aborted = True
1413
 
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
1414
 
                "Missing parent")
1415
 
 
1416
 
    def update_basis_by_delta(self, delta, new_revid):
1417
 
        """Update the parents of this tree after a commit.
1418
 
 
1419
 
        This gives the tree one parent, with revision id new_revid. The
1420
 
        inventory delta is applied to the current basis tree to generate the
1421
 
        inventory for the parent new_revid, and all other parent trees are
1422
 
        discarded.
1423
 
 
1424
 
        Note that an exception during the operation of this method will leave
1425
 
        the dirstate in a corrupt state where it should not be saved.
1426
 
 
1427
 
        Finally, we expect all changes to be synchronising the basis tree with
1428
 
        the working tree.
1429
 
 
1430
 
        :param new_revid: The new revision id for the trees parent.
1431
 
        :param delta: An inventory delta (see apply_inventory_delta) describing
1432
 
            the changes from the current left most parent revision to new_revid.
1433
 
        """
1434
 
        self._read_dirblocks_if_needed()
1435
 
        self._discard_merge_parents()
1436
 
        if self._ghosts != []:
1437
 
            raise NotImplementedError(self.update_basis_by_delta)
1438
 
        if len(self._parents) == 0:
1439
 
            # setup a blank tree, the most simple way.
1440
 
            empty_parent = DirState.NULL_PARENT_DETAILS
1441
 
            for entry in self._iter_entries():
1442
 
                entry[1].append(empty_parent)
1443
 
            self._parents.append(new_revid)
1444
 
 
1445
 
        self._parents[0] = new_revid
1446
 
 
1447
 
        delta = sorted(delta, reverse=True)
1448
 
        adds = []
1449
 
        changes = []
1450
 
        deletes = []
1451
 
        # The paths this function accepts are unicode and must be encoded as we
1452
 
        # go.
1453
 
        encode = cache_utf8.encode
1454
 
        inv_to_entry = self._inv_entry_to_details
1455
 
        # delta is now (deletes, changes), (adds) in reverse lexographical
1456
 
        # order.
1457
 
        # deletes in reverse lexographic order are safe to process in situ.
1458
 
        # renames are not, as a rename from any path could go to a path
1459
 
        # lexographically lower, so we transform renames into delete, add pairs,
1460
 
        # expanding them recursively as needed.
1461
 
        # At the same time, to reduce interface friction we convert the input
1462
 
        # inventory entries to dirstate.
1463
 
        root_only = ('', '')
1464
 
        # Accumulate parent references (path_utf8, id), to check for parentless
1465
 
        # items or items placed under files/links/tree-references. We get
1466
 
        # references from every item in the delta that is not a deletion and
1467
 
        # is not itself the root.
1468
 
        parents = set()
1469
 
        # Added ids must not be in the dirstate already. This set holds those
1470
 
        # ids.
1471
 
        new_ids = set()
1472
 
        for old_path, new_path, file_id, inv_entry in delta:
1473
 
            if inv_entry is not None and file_id != inv_entry.file_id:
1474
 
                raise errors.InconsistentDelta(new_path, file_id,
1475
 
                    "mismatched entry file_id %r" % inv_entry)
1476
 
            if new_path is not None:
1477
 
                if inv_entry is None:
1478
 
                    raise errors.InconsistentDelta(new_path, file_id,
1479
 
                        "new_path with no entry")
1480
 
                new_path_utf8 = encode(new_path)
1481
 
                # note the parent for validation
1482
 
                dirname_utf8, basename_utf8 = osutils.split(new_path_utf8)
1483
 
                if basename_utf8:
1484
 
                    parents.add((dirname_utf8, inv_entry.parent_id))
1485
 
            if old_path is None:
1486
 
                adds.append((None, encode(new_path), file_id,
1487
 
                    inv_to_entry(inv_entry), True))
1488
 
                new_ids.add(file_id)
1489
 
            elif new_path is None:
1490
 
                deletes.append((encode(old_path), None, file_id, None, True))
1491
 
            elif (old_path, new_path) != root_only:
1492
 
                # Renames:
1493
 
                # Because renames must preserve their children we must have
1494
 
                # processed all relocations and removes before hand. The sort
1495
 
                # order ensures we've examined the child paths, but we also
1496
 
                # have to execute the removals, or the split to an add/delete
1497
 
                # pair will result in the deleted item being reinserted, or
1498
 
                # renamed items being reinserted twice - and possibly at the
1499
 
                # wrong place. Splitting into a delete/add pair also simplifies
1500
 
                # the handling of entries with ('f', ...), ('r' ...) because
1501
 
                # the target of the 'r' is old_path here, and we add that to
1502
 
                # deletes, meaning that the add handler does not need to check
1503
 
                # for 'r' items on every pass.
1504
 
                self._update_basis_apply_deletes(deletes)
1505
 
                deletes = []
1506
 
                # Split into an add/delete pair recursively.
1507
 
                adds.append((None, new_path_utf8, file_id,
1508
 
                    inv_to_entry(inv_entry), False))
1509
 
                # Expunge deletes that we've seen so that deleted/renamed
1510
 
                # children of a rename directory are handled correctly.
1511
 
                new_deletes = reversed(list(self._iter_child_entries(1,
1512
 
                    encode(old_path))))
1513
 
                # Remove the current contents of the tree at orig_path, and
1514
 
                # reinsert at the correct new path.
1515
 
                for entry in new_deletes:
1516
 
                    if entry[0][0]:
1517
 
                        source_path = entry[0][0] + '/' + entry[0][1]
1518
 
                    else:
1519
 
                        source_path = entry[0][1]
1520
 
                    if new_path_utf8:
1521
 
                        target_path = new_path_utf8 + source_path[len(old_path):]
1522
 
                    else:
1523
 
                        if old_path == '':
1524
 
                            raise AssertionError("cannot rename directory to"
1525
 
                                " itself")
1526
 
                        target_path = source_path[len(old_path) + 1:]
1527
 
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1528
 
                    deletes.append(
1529
 
                        (source_path, target_path, entry[0][2], None, False))
1530
 
                deletes.append(
1531
 
                    (encode(old_path), new_path, file_id, None, False))
1532
 
            else:
1533
 
                # changes to just the root should not require remove/insertion
1534
 
                # of everything.
1535
 
                changes.append((encode(old_path), encode(new_path), file_id,
1536
 
                    inv_to_entry(inv_entry)))
1537
 
        self._check_delta_ids_absent(new_ids, delta, 1)
1538
 
        try:
1539
 
            # Finish expunging deletes/first half of renames.
1540
 
            self._update_basis_apply_deletes(deletes)
1541
 
            # Reinstate second half of renames and new paths.
1542
 
            self._update_basis_apply_adds(adds)
1543
 
            # Apply in-situ changes.
1544
 
            self._update_basis_apply_changes(changes)
1545
 
            # Validate parents
1546
 
            self._after_delta_check_parents(parents, 1)
1547
 
        except errors.BzrError, e:
1548
 
            self._changes_aborted = True
1549
 
            if 'integrity error' not in str(e):
1550
 
                raise
1551
 
            # _get_entry raises BzrError when a request is inconsistent; we
1552
 
            # want such errors to be shown as InconsistentDelta - and that 
1553
 
            # fits the behaviour we trigger. Partof this is driven by dirstate
1554
 
            # only supporting deltas that turn the basis into a closer fit to
1555
 
            # the active tree.
1556
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1557
 
 
1558
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1559
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
1560
 
        self._id_index = None
1561
 
        return
1562
 
 
1563
 
    def _check_delta_ids_absent(self, new_ids, delta, tree_index):
1564
 
        """Check that none of the file_ids in new_ids are present in a tree."""
1565
 
        if not new_ids:
1566
 
            return
1567
 
        id_index = self._get_id_index()
1568
 
        for file_id in new_ids:
1569
 
            for key in id_index.get(file_id, []):
1570
 
                block_i, entry_i, d_present, f_present = \
1571
 
                    self._get_block_entry_index(key[0], key[1], tree_index)
1572
 
                if not f_present:
1573
 
                    # In a different tree
1574
 
                    continue
1575
 
                entry = self._dirblocks[block_i][1][entry_i]
1576
 
                if entry[0][2] != file_id:
1577
 
                    # Different file_id, so not what we want.
1578
 
                    continue
1579
 
                # NB: No changes made before this helper is called, so no need
1580
 
                # to set the _changes_aborted flag.
1581
 
                raise errors.InconsistentDelta(
1582
 
                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
1583
 
                    "This file_id is new in the delta but already present in "
1584
 
                    "the target")
1585
 
 
1586
 
    def _update_basis_apply_adds(self, adds):
1587
 
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1588
 
 
1589
 
        They may be adds, or renames that have been split into add/delete
1590
 
        pairs.
1591
 
 
1592
 
        :param adds: A sequence of adds. Each add is a tuple:
1593
 
            (None, new_path_utf8, file_id, (entry_details), real_add). real_add
1594
 
            is False when the add is the second half of a remove-and-reinsert
1595
 
            pair created to handle renames and deletes.
1596
 
        """
1597
 
        # Adds are accumulated partly from renames, so can be in any input
1598
 
        # order - sort it.
1599
 
        adds.sort()
1600
 
        # adds is now in lexographic order, which places all parents before
1601
 
        # their children, so we can process it linearly.
1602
 
        absent = 'ar'
1603
 
        for old_path, new_path, file_id, new_details, real_add in adds:
1604
 
            # the entry for this file_id must be in tree 0.
1605
 
            entry = self._get_entry(0, file_id, new_path)
1606
 
            if entry[0] is None or entry[0][2] != file_id:
1607
 
                self._changes_aborted = True
1608
 
                raise errors.InconsistentDelta(new_path, file_id,
1609
 
                    'working tree does not contain new entry')
1610
 
            if real_add and entry[1][1][0] not in absent:
1611
 
                self._changes_aborted = True
1612
 
                raise errors.InconsistentDelta(new_path, file_id,
1613
 
                    'The entry was considered to be a genuinely new record,'
1614
 
                    ' but there was already an old record for it.')
1615
 
            # We don't need to update the target of an 'r' because the handling
1616
 
            # of renames turns all 'r' situations into a delete at the original
1617
 
            # location.
1618
 
            entry[1][1] = new_details
1619
 
 
1620
 
    def _update_basis_apply_changes(self, changes):
1621
 
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1622
 
 
1623
 
        :param adds: A sequence of changes. Each change is a tuple:
1624
 
            (path_utf8, path_utf8, file_id, (entry_details))
1625
 
        """
1626
 
        absent = 'ar'
1627
 
        for old_path, new_path, file_id, new_details in changes:
1628
 
            # the entry for this file_id must be in tree 0.
1629
 
            entry = self._get_entry(0, file_id, new_path)
1630
 
            if entry[0] is None or entry[0][2] != file_id:
1631
 
                self._changes_aborted = True
1632
 
                raise errors.InconsistentDelta(new_path, file_id,
1633
 
                    'working tree does not contain new entry')
1634
 
            if (entry[1][0][0] in absent or
1635
 
                entry[1][1][0] in absent):
1636
 
                self._changes_aborted = True
1637
 
                raise errors.InconsistentDelta(new_path, file_id,
1638
 
                    'changed considered absent')
1639
 
            entry[1][1] = new_details
1640
 
 
1641
 
    def _update_basis_apply_deletes(self, deletes):
1642
 
        """Apply a sequence of deletes to tree 1 during update_basis_by_delta.
1643
 
 
1644
 
        They may be deletes, or renames that have been split into add/delete
1645
 
        pairs.
1646
 
 
1647
 
        :param deletes: A sequence of deletes. Each delete is a tuple:
1648
 
            (old_path_utf8, new_path_utf8, file_id, None, real_delete).
1649
 
            real_delete is True when the desired outcome is an actual deletion
1650
 
            rather than the rename handling logic temporarily deleting a path
1651
 
            during the replacement of a parent.
1652
 
        """
1653
 
        null = DirState.NULL_PARENT_DETAILS
1654
 
        for old_path, new_path, file_id, _, real_delete in deletes:
1655
 
            if real_delete != (new_path is None):
1656
 
                self._changes_aborted = True
1657
 
                raise AssertionError("bad delete delta")
1658
 
            # the entry for this file_id must be in tree 1.
1659
 
            dirname, basename = osutils.split(old_path)
1660
 
            block_index, entry_index, dir_present, file_present = \
1661
 
                self._get_block_entry_index(dirname, basename, 1)
1662
 
            if not file_present:
1663
 
                self._changes_aborted = True
1664
 
                raise errors.InconsistentDelta(old_path, file_id,
1665
 
                    'basis tree does not contain removed entry')
1666
 
            entry = self._dirblocks[block_index][1][entry_index]
1667
 
            if entry[0][2] != file_id:
1668
 
                self._changes_aborted = True
1669
 
                raise errors.InconsistentDelta(old_path, file_id,
1670
 
                    'mismatched file_id in tree 1')
1671
 
            if real_delete:
1672
 
                if entry[1][0][0] != 'a':
1673
 
                    self._changes_aborted = True
1674
 
                    raise errors.InconsistentDelta(old_path, file_id,
1675
 
                            'This was marked as a real delete, but the WT state'
1676
 
                            ' claims that it still exists and is versioned.')
1677
 
                del self._dirblocks[block_index][1][entry_index]
1678
 
            else:
1679
 
                if entry[1][0][0] == 'a':
1680
 
                    self._changes_aborted = True
1681
 
                    raise errors.InconsistentDelta(old_path, file_id,
1682
 
                        'The entry was considered a rename, but the source path'
1683
 
                        ' is marked as absent.')
1684
 
                    # For whatever reason, we were asked to rename an entry
1685
 
                    # that was originally marked as deleted. This could be
1686
 
                    # because we are renaming the parent directory, and the WT
1687
 
                    # current state has the file marked as deleted.
1688
 
                elif entry[1][0][0] == 'r':
1689
 
                    # implement the rename
1690
 
                    del self._dirblocks[block_index][1][entry_index]
1691
 
                else:
1692
 
                    # it is being resurrected here, so blank it out temporarily.
1693
 
                    self._dirblocks[block_index][1][entry_index][1][1] = null
1694
 
 
1695
 
    def _after_delta_check_parents(self, parents, index):
1696
 
        """Check that parents required by the delta are all intact.
1697
 
        
1698
 
        :param parents: An iterable of (path_utf8, file_id) tuples which are
1699
 
            required to be present in tree 'index' at path_utf8 with id file_id
1700
 
            and be a directory.
1701
 
        :param index: The column in the dirstate to check for parents in.
1702
 
        """
1703
 
        for dirname_utf8, file_id in parents:
1704
 
            # Get the entry - the ensures that file_id, dirname_utf8 exists and
1705
 
            # has the right file id.
1706
 
            entry = self._get_entry(index, file_id, dirname_utf8)
1707
 
            if entry[1] is None:
1708
 
                self._changes_aborted = True
1709
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1710
 
                    file_id, "This parent is not present.")
1711
 
            # Parents of things must be directories
1712
 
            if entry[1][index][0] != 'd':
1713
 
                self._changes_aborted = True
1714
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1715
 
                    file_id, "This parent is not a directory.")
1716
 
 
1717
 
    def _observed_sha1(self, entry, sha1, stat_value,
1718
 
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
1719
 
        """Note the sha1 of a file.
1720
 
 
1721
 
        :param entry: The entry the sha1 is for.
1722
 
        :param sha1: The observed sha1.
1723
 
        :param stat_value: The os.lstat for the file.
1724
 
        """
1725
 
        try:
1726
 
            minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
1727
 
        except KeyError:
1728
 
            # Unhandled kind
1729
 
            return None
1730
 
        packed_stat = _pack_stat(stat_value)
1731
 
        if minikind == 'f':
1732
 
            if self._cutoff_time is None:
1733
 
                self._sha_cutoff_time()
1734
 
            if (stat_value.st_mtime < self._cutoff_time
1735
 
                and stat_value.st_ctime < self._cutoff_time):
1736
 
                entry[1][0] = ('f', sha1, entry[1][0][2], entry[1][0][3],
1737
 
                    packed_stat)
1738
 
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1739
 
 
1740
 
    def _sha_cutoff_time(self):
1741
 
        """Return cutoff time.
1742
 
 
1743
 
        Files modified more recently than this time are at risk of being
1744
 
        undetectably modified and so can't be cached.
1745
 
        """
1746
 
        # Cache the cutoff time as long as we hold a lock.
1747
 
        # time.time() isn't super expensive (approx 3.38us), but
1748
 
        # when you call it 50,000 times it adds up.
1749
 
        # For comparison, os.lstat() costs 7.2us if it is hot.
1750
 
        self._cutoff_time = int(time.time()) - 3
1751
 
        return self._cutoff_time
1752
 
 
1753
 
    def _lstat(self, abspath, entry):
1754
 
        """Return the os.lstat value for this path."""
1755
 
        return os.lstat(abspath)
1756
 
 
1757
 
    def _sha1_file_and_mutter(self, abspath):
1758
 
        # when -Dhashcache is turned on, this is monkey-patched in to log
1759
 
        # file reads
1760
 
        trace.mutter("dirstate sha1 " + abspath)
1761
 
        return self._sha1_provider.sha1(abspath)
1762
 
 
1763
 
    def _is_executable(self, mode, old_executable):
1764
 
        """Is this file executable?"""
1765
 
        return bool(S_IEXEC & mode)
1766
 
 
1767
 
    def _is_executable_win32(self, mode, old_executable):
1768
 
        """On win32 the executable bit is stored in the dirstate."""
1769
 
        return old_executable
1770
 
 
1771
 
    if sys.platform == 'win32':
1772
 
        _is_executable = _is_executable_win32
1773
 
 
1774
 
    def _read_link(self, abspath, old_link):
1775
 
        """Read the target of a symlink"""
1776
 
        # TODO: jam 200700301 On Win32, this could just return the value
1777
 
        #       already in memory. However, this really needs to be done at a
1778
 
        #       higher level, because there either won't be anything on disk,
1779
 
        #       or the thing on disk will be a file.
1780
 
        fs_encoding = osutils._fs_enc
1781
 
        if isinstance(abspath, unicode):
1782
 
            # abspath is defined as the path to pass to lstat. readlink is
1783
 
            # buggy in python < 2.6 (it doesn't encode unicode path into FS
1784
 
            # encoding), so we need to encode ourselves knowing that unicode
1785
 
            # paths are produced by UnicodeDirReader on purpose.
1786
 
            abspath = abspath.encode(fs_encoding)
1787
 
        target = os.readlink(abspath)
1788
 
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
1789
 
            # Change encoding if needed
1790
 
            target = target.decode(fs_encoding).encode('UTF-8')
1791
 
        return target
1792
 
 
1793
 
    def get_ghosts(self):
1794
 
        """Return a list of the parent tree revision ids that are ghosts."""
1795
 
        self._read_header_if_needed()
1796
 
        return self._ghosts
1797
 
 
1798
 
    def get_lines(self):
1799
 
        """Serialise the entire dirstate to a sequence of lines."""
1800
 
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1801
 
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1802
 
            # read whats on disk.
1803
 
            self._state_file.seek(0)
1804
 
            return self._state_file.readlines()
1805
 
        lines = []
1806
 
        lines.append(self._get_parents_line(self.get_parent_ids()))
1807
 
        lines.append(self._get_ghosts_line(self._ghosts))
1808
 
        # append the root line which is special cased
1809
 
        lines.extend(map(self._entry_to_line, self._iter_entries()))
1810
 
        return self._get_output_lines(lines)
1811
 
 
1812
 
    def _get_ghosts_line(self, ghost_ids):
1813
 
        """Create a line for the state file for ghost information."""
1814
 
        return '\0'.join([str(len(ghost_ids))] + ghost_ids)
1815
 
 
1816
 
    def _get_parents_line(self, parent_ids):
1817
 
        """Create a line for the state file for parents information."""
1818
 
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1819
 
 
1820
 
    def _get_fields_to_entry(self):
1821
 
        """Get a function which converts entry fields into a entry record.
1822
 
 
1823
 
        This handles size and executable, as well as parent records.
1824
 
 
1825
 
        :return: A function which takes a list of fields, and returns an
1826
 
            appropriate record for storing in memory.
1827
 
        """
1828
 
        # This is intentionally unrolled for performance
1829
 
        num_present_parents = self._num_present_parents()
1830
 
        if num_present_parents == 0:
1831
 
            def fields_to_entry_0_parents(fields, _int=int):
1832
 
                path_name_file_id_key = (fields[0], fields[1], fields[2])
1833
 
                return (path_name_file_id_key, [
1834
 
                    ( # Current tree
1835
 
                        fields[3],                # minikind
1836
 
                        fields[4],                # fingerprint
1837
 
                        _int(fields[5]),          # size
1838
 
                        fields[6] == 'y',         # executable
1839
 
                        fields[7],                # packed_stat or revision_id
1840
 
                    )])
1841
 
            return fields_to_entry_0_parents
1842
 
        elif num_present_parents == 1:
1843
 
            def fields_to_entry_1_parent(fields, _int=int):
1844
 
                path_name_file_id_key = (fields[0], fields[1], fields[2])
1845
 
                return (path_name_file_id_key, [
1846
 
                    ( # Current tree
1847
 
                        fields[3],                # minikind
1848
 
                        fields[4],                # fingerprint
1849
 
                        _int(fields[5]),          # size
1850
 
                        fields[6] == 'y',         # executable
1851
 
                        fields[7],                # packed_stat or revision_id
1852
 
                    ),
1853
 
                    ( # Parent 1
1854
 
                        fields[8],                # minikind
1855
 
                        fields[9],                # fingerprint
1856
 
                        _int(fields[10]),         # size
1857
 
                        fields[11] == 'y',        # executable
1858
 
                        fields[12],               # packed_stat or revision_id
1859
 
                    ),
1860
 
                    ])
1861
 
            return fields_to_entry_1_parent
1862
 
        elif num_present_parents == 2:
1863
 
            def fields_to_entry_2_parents(fields, _int=int):
1864
 
                path_name_file_id_key = (fields[0], fields[1], fields[2])
1865
 
                return (path_name_file_id_key, [
1866
 
                    ( # Current tree
1867
 
                        fields[3],                # minikind
1868
 
                        fields[4],                # fingerprint
1869
 
                        _int(fields[5]),          # size
1870
 
                        fields[6] == 'y',         # executable
1871
 
                        fields[7],                # packed_stat or revision_id
1872
 
                    ),
1873
 
                    ( # Parent 1
1874
 
                        fields[8],                # minikind
1875
 
                        fields[9],                # fingerprint
1876
 
                        _int(fields[10]),         # size
1877
 
                        fields[11] == 'y',        # executable
1878
 
                        fields[12],               # packed_stat or revision_id
1879
 
                    ),
1880
 
                    ( # Parent 2
1881
 
                        fields[13],               # minikind
1882
 
                        fields[14],               # fingerprint
1883
 
                        _int(fields[15]),         # size
1884
 
                        fields[16] == 'y',        # executable
1885
 
                        fields[17],               # packed_stat or revision_id
1886
 
                    ),
1887
 
                    ])
1888
 
            return fields_to_entry_2_parents
1889
 
        else:
1890
 
            def fields_to_entry_n_parents(fields, _int=int):
1891
 
                path_name_file_id_key = (fields[0], fields[1], fields[2])
1892
 
                trees = [(fields[cur],                # minikind
1893
 
                          fields[cur+1],              # fingerprint
1894
 
                          _int(fields[cur+2]),        # size
1895
 
                          fields[cur+3] == 'y',       # executable
1896
 
                          fields[cur+4],              # stat or revision_id
1897
 
                         ) for cur in xrange(3, len(fields)-1, 5)]
1898
 
                return path_name_file_id_key, trees
1899
 
            return fields_to_entry_n_parents
1900
 
 
1901
 
    def get_parent_ids(self):
1902
 
        """Return a list of the parent tree ids for the directory state."""
1903
 
        self._read_header_if_needed()
1904
 
        return list(self._parents)
1905
 
 
1906
 
    def _get_block_entry_index(self, dirname, basename, tree_index):
1907
 
        """Get the coordinates for a path in the state structure.
1908
 
 
1909
 
        :param dirname: The utf8 dirname to lookup.
1910
 
        :param basename: The utf8 basename to lookup.
1911
 
        :param tree_index: The index of the tree for which this lookup should
1912
 
            be attempted.
1913
 
        :return: A tuple describing where the path is located, or should be
1914
 
            inserted. The tuple contains four fields: the block index, the row
1915
 
            index, the directory is present (boolean), the entire path is
1916
 
            present (boolean).  There is no guarantee that either
1917
 
            coordinate is currently reachable unless the found field for it is
1918
 
            True. For instance, a directory not present in the searched tree
1919
 
            may be returned with a value one greater than the current highest
1920
 
            block offset. The directory present field will always be True when
1921
 
            the path present field is True. The directory present field does
1922
 
            NOT indicate that the directory is present in the searched tree,
1923
 
            rather it indicates that there are at least some files in some
1924
 
            tree present there.
1925
 
        """
1926
 
        self._read_dirblocks_if_needed()
1927
 
        key = dirname, basename, ''
1928
 
        block_index, present = self._find_block_index_from_key(key)
1929
 
        if not present:
1930
 
            # no such directory - return the dir index and 0 for the row.
1931
 
            return block_index, 0, False, False
1932
 
        block = self._dirblocks[block_index][1] # access the entries only
1933
 
        entry_index, present = self._find_entry_index(key, block)
1934
 
        # linear search through entries at this path to find the one
1935
 
        # requested.
1936
 
        while entry_index < len(block) and block[entry_index][0][1] == basename:
1937
 
            if block[entry_index][1][tree_index][0] not in 'ar':
1938
 
                # neither absent or relocated
1939
 
                return block_index, entry_index, True, True
1940
 
            entry_index += 1
1941
 
        return block_index, entry_index, True, False
1942
 
 
1943
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
1944
 
        """Get the dirstate entry for path in tree tree_index.
1945
 
 
1946
 
        If either file_id or path is supplied, it is used as the key to lookup.
1947
 
        If both are supplied, the fastest lookup is used, and an error is
1948
 
        raised if they do not both point at the same row.
1949
 
 
1950
 
        :param tree_index: The index of the tree we wish to locate this path
1951
 
            in. If the path is present in that tree, the entry containing its
1952
 
            details is returned, otherwise (None, None) is returned
1953
 
            0 is the working tree, higher indexes are successive parent
1954
 
            trees.
1955
 
        :param fileid_utf8: A utf8 file_id to look up.
1956
 
        :param path_utf8: An utf8 path to be looked up.
1957
 
        :param include_deleted: If True, and performing a lookup via
1958
 
            fileid_utf8 rather than path_utf8, return an entry for deleted
1959
 
            (absent) paths.
1960
 
        :return: The dirstate entry tuple for path, or (None, None)
1961
 
        """
1962
 
        self._read_dirblocks_if_needed()
1963
 
        if path_utf8 is not None:
1964
 
            if type(path_utf8) is not str:
1965
 
                raise errors.BzrError('path_utf8 is not a str: %s %r'
1966
 
                    % (type(path_utf8), path_utf8))
1967
 
            # path lookups are faster
1968
 
            dirname, basename = osutils.split(path_utf8)
1969
 
            block_index, entry_index, dir_present, file_present = \
1970
 
                self._get_block_entry_index(dirname, basename, tree_index)
1971
 
            if not file_present:
1972
 
                return None, None
1973
 
            entry = self._dirblocks[block_index][1][entry_index]
1974
 
            if not (entry[0][2] and entry[1][tree_index][0] not in ('a', 'r')):
1975
 
                raise AssertionError('unversioned entry?')
1976
 
            if fileid_utf8:
1977
 
                if entry[0][2] != fileid_utf8:
1978
 
                    self._changes_aborted = True
1979
 
                    raise errors.BzrError('integrity error ? : mismatching'
1980
 
                                          ' tree_index, file_id and path')
1981
 
            return entry
1982
 
        else:
1983
 
            possible_keys = self._get_id_index().get(fileid_utf8, None)
1984
 
            if not possible_keys:
1985
 
                return None, None
1986
 
            for key in possible_keys:
1987
 
                block_index, present = \
1988
 
                    self._find_block_index_from_key(key)
1989
 
                # strange, probably indicates an out of date
1990
 
                # id index - for now, allow this.
1991
 
                if not present:
1992
 
                    continue
1993
 
                # WARNING: DO not change this code to use _get_block_entry_index
1994
 
                # as that function is not suitable: it does not use the key
1995
 
                # to lookup, and thus the wrong coordinates are returned.
1996
 
                block = self._dirblocks[block_index][1]
1997
 
                entry_index, present = self._find_entry_index(key, block)
1998
 
                if present:
1999
 
                    entry = self._dirblocks[block_index][1][entry_index]
2000
 
                    # TODO: We might want to assert that entry[0][2] ==
2001
 
                    #       fileid_utf8.
2002
 
                    if entry[1][tree_index][0] in 'fdlt':
2003
 
                        # this is the result we are looking for: the
2004
 
                        # real home of this file_id in this tree.
2005
 
                        return entry
2006
 
                    if entry[1][tree_index][0] == 'a':
2007
 
                        # there is no home for this entry in this tree
2008
 
                        if include_deleted:
2009
 
                            return entry
2010
 
                        return None, None
2011
 
                    if entry[1][tree_index][0] != 'r':
2012
 
                        raise AssertionError(
2013
 
                            "entry %r has invalid minikind %r for tree %r" \
2014
 
                            % (entry,
2015
 
                               entry[1][tree_index][0],
2016
 
                               tree_index))
2017
 
                    real_path = entry[1][tree_index][1]
2018
 
                    return self._get_entry(tree_index, fileid_utf8=fileid_utf8,
2019
 
                        path_utf8=real_path)
2020
 
            return None, None
2021
 
 
2022
 
    @classmethod
2023
 
    def initialize(cls, path, sha1_provider=None):
2024
 
        """Create a new dirstate on path.
2025
 
 
2026
 
        The new dirstate will be an empty tree - that is it has no parents,
2027
 
        and only a root node - which has id ROOT_ID.
2028
 
 
2029
 
        :param path: The name of the file for the dirstate.
2030
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
2031
 
            If None, a DefaultSHA1Provider is used.
2032
 
        :return: A write-locked DirState object.
2033
 
        """
2034
 
        # This constructs a new DirState object on a path, sets the _state_file
2035
 
        # to a new empty file for that path. It then calls _set_data() with our
2036
 
        # stock empty dirstate information - a root with ROOT_ID, no children,
2037
 
        # and no parents. Finally it calls save() to ensure that this data will
2038
 
        # persist.
2039
 
        if sha1_provider is None:
2040
 
            sha1_provider = DefaultSHA1Provider()
2041
 
        result = cls(path, sha1_provider)
2042
 
        # root dir and root dir contents with no children.
2043
 
        empty_tree_dirblocks = [('', []), ('', [])]
2044
 
        # a new root directory, with a NULLSTAT.
2045
 
        empty_tree_dirblocks[0][1].append(
2046
 
            (('', '', inventory.ROOT_ID), [
2047
 
                ('d', '', 0, False, DirState.NULLSTAT),
2048
 
            ]))
2049
 
        result.lock_write()
2050
 
        try:
2051
 
            result._set_data([], empty_tree_dirblocks)
2052
 
            result.save()
2053
 
        except:
2054
 
            result.unlock()
2055
 
            raise
2056
 
        return result
2057
 
 
2058
 
    @staticmethod
2059
 
    def _inv_entry_to_details(inv_entry):
2060
 
        """Convert an inventory entry (from a revision tree) to state details.
2061
 
 
2062
 
        :param inv_entry: An inventory entry whose sha1 and link targets can be
2063
 
            relied upon, and which has a revision set.
2064
 
        :return: A details tuple - the details for a single tree at a path +
2065
 
            id.
2066
 
        """
2067
 
        kind = inv_entry.kind
2068
 
        minikind = DirState._kind_to_minikind[kind]
2069
 
        tree_data = inv_entry.revision
2070
 
        if kind == 'directory':
2071
 
            fingerprint = ''
2072
 
            size = 0
2073
 
            executable = False
2074
 
        elif kind == 'symlink':
2075
 
            if inv_entry.symlink_target is None:
2076
 
                fingerprint = ''
2077
 
            else:
2078
 
                fingerprint = inv_entry.symlink_target.encode('utf8')
2079
 
            size = 0
2080
 
            executable = False
2081
 
        elif kind == 'file':
2082
 
            fingerprint = inv_entry.text_sha1 or ''
2083
 
            size = inv_entry.text_size or 0
2084
 
            executable = inv_entry.executable
2085
 
        elif kind == 'tree-reference':
2086
 
            fingerprint = inv_entry.reference_revision or ''
2087
 
            size = 0
2088
 
            executable = False
2089
 
        else:
2090
 
            raise Exception("can't pack %s" % inv_entry)
2091
 
        return (minikind, fingerprint, size, executable, tree_data)
2092
 
 
2093
 
    def _iter_child_entries(self, tree_index, path_utf8):
2094
 
        """Iterate over all the entries that are children of path_utf.
2095
 
 
2096
 
        This only returns entries that are present (not in 'a', 'r') in
2097
 
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
2098
 
        results may differ from that obtained if paths were statted to
2099
 
        determine what ones were directories.
2100
 
 
2101
 
        Asking for the children of a non-directory will return an empty
2102
 
        iterator.
2103
 
        """
2104
 
        pending_dirs = []
2105
 
        next_pending_dirs = [path_utf8]
2106
 
        absent = 'ar'
2107
 
        while next_pending_dirs:
2108
 
            pending_dirs = next_pending_dirs
2109
 
            next_pending_dirs = []
2110
 
            for path in pending_dirs:
2111
 
                block_index, present = self._find_block_index_from_key(
2112
 
                    (path, '', ''))
2113
 
                if block_index == 0:
2114
 
                    block_index = 1
2115
 
                    if len(self._dirblocks) == 1:
2116
 
                        # asked for the children of the root with no other
2117
 
                        # contents.
2118
 
                        return
2119
 
                if not present:
2120
 
                    # children of a non-directory asked for.
2121
 
                    continue
2122
 
                block = self._dirblocks[block_index]
2123
 
                for entry in block[1]:
2124
 
                    kind = entry[1][tree_index][0]
2125
 
                    if kind not in absent:
2126
 
                        yield entry
2127
 
                    if kind == 'd':
2128
 
                        if entry[0][0]:
2129
 
                            path = entry[0][0] + '/' + entry[0][1]
2130
 
                        else:
2131
 
                            path = entry[0][1]
2132
 
                        next_pending_dirs.append(path)
2133
 
 
2134
 
    def _iter_entries(self):
2135
 
        """Iterate over all the entries in the dirstate.
2136
 
 
2137
 
        Each yelt item is an entry in the standard format described in the
2138
 
        docstring of bzrlib.dirstate.
2139
 
        """
2140
 
        self._read_dirblocks_if_needed()
2141
 
        for directory in self._dirblocks:
2142
 
            for entry in directory[1]:
2143
 
                yield entry
2144
 
 
2145
 
    def _get_id_index(self):
2146
 
        """Get an id index of self._dirblocks."""
2147
 
        if self._id_index is None:
2148
 
            id_index = {}
2149
 
            for key, tree_details in self._iter_entries():
2150
 
                id_index.setdefault(key[2], set()).add(key)
2151
 
            self._id_index = id_index
2152
 
        return self._id_index
2153
 
 
2154
 
    def _get_output_lines(self, lines):
2155
 
        """Format lines for final output.
2156
 
 
2157
 
        :param lines: A sequence of lines containing the parents list and the
2158
 
            path lines.
2159
 
        """
2160
 
        output_lines = [DirState.HEADER_FORMAT_3]
2161
 
        lines.append('') # a final newline
2162
 
        inventory_text = '\0\n\0'.join(lines)
2163
 
        output_lines.append('crc32: %s\n' % (zlib.crc32(inventory_text),))
2164
 
        # -3, 1 for num parents, 1 for ghosts, 1 for final newline
2165
 
        num_entries = len(lines)-3
2166
 
        output_lines.append('num_entries: %s\n' % (num_entries,))
2167
 
        output_lines.append(inventory_text)
2168
 
        return output_lines
2169
 
 
2170
 
    def _make_deleted_row(self, fileid_utf8, parents):
2171
 
        """Return a deleted row for fileid_utf8."""
2172
 
        return ('/', 'RECYCLED.BIN', 'file', fileid_utf8, 0, DirState.NULLSTAT,
2173
 
            ''), parents
2174
 
 
2175
 
    def _num_present_parents(self):
2176
 
        """The number of parent entries in each record row."""
2177
 
        return len(self._parents) - len(self._ghosts)
2178
 
 
2179
 
    @staticmethod
2180
 
    def on_file(path, sha1_provider=None):
2181
 
        """Construct a DirState on the file at path "path".
2182
 
 
2183
 
        :param path: The path at which the dirstate file on disk should live.
2184
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
2185
 
            If None, a DefaultSHA1Provider is used.
2186
 
        :return: An unlocked DirState object, associated with the given path.
2187
 
        """
2188
 
        if sha1_provider is None:
2189
 
            sha1_provider = DefaultSHA1Provider()
2190
 
        result = DirState(path, sha1_provider)
2191
 
        return result
2192
 
 
2193
 
    def _read_dirblocks_if_needed(self):
2194
 
        """Read in all the dirblocks from the file if they are not in memory.
2195
 
 
2196
 
        This populates self._dirblocks, and sets self._dirblock_state to
2197
 
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
2198
 
        loading.
2199
 
        """
2200
 
        self._read_header_if_needed()
2201
 
        if self._dirblock_state == DirState.NOT_IN_MEMORY:
2202
 
            _read_dirblocks(self)
2203
 
 
2204
 
    def _read_header(self):
2205
 
        """This reads in the metadata header, and the parent ids.
2206
 
 
2207
 
        After reading in, the file should be positioned at the null
2208
 
        just before the start of the first record in the file.
2209
 
 
2210
 
        :return: (expected crc checksum, number of entries, parent list)
2211
 
        """
2212
 
        self._read_prelude()
2213
 
        parent_line = self._state_file.readline()
2214
 
        info = parent_line.split('\0')
2215
 
        num_parents = int(info[0])
2216
 
        self._parents = info[1:-1]
2217
 
        ghost_line = self._state_file.readline()
2218
 
        info = ghost_line.split('\0')
2219
 
        num_ghosts = int(info[1])
2220
 
        self._ghosts = info[2:-1]
2221
 
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
2222
 
        self._end_of_header = self._state_file.tell()
2223
 
 
2224
 
    def _read_header_if_needed(self):
2225
 
        """Read the header of the dirstate file if needed."""
2226
 
        # inline this as it will be called a lot
2227
 
        if not self._lock_token:
2228
 
            raise errors.ObjectNotLocked(self)
2229
 
        if self._header_state == DirState.NOT_IN_MEMORY:
2230
 
            self._read_header()
2231
 
 
2232
 
    def _read_prelude(self):
2233
 
        """Read in the prelude header of the dirstate file.
2234
 
 
2235
 
        This only reads in the stuff that is not connected to the crc
2236
 
        checksum. The position will be correct to read in the rest of
2237
 
        the file and check the checksum after this point.
2238
 
        The next entry in the file should be the number of parents,
2239
 
        and their ids. Followed by a newline.
2240
 
        """
2241
 
        header = self._state_file.readline()
2242
 
        if header != DirState.HEADER_FORMAT_3:
2243
 
            raise errors.BzrError(
2244
 
                'invalid header line: %r' % (header,))
2245
 
        crc_line = self._state_file.readline()
2246
 
        if not crc_line.startswith('crc32: '):
2247
 
            raise errors.BzrError('missing crc32 checksum: %r' % crc_line)
2248
 
        self.crc_expected = int(crc_line[len('crc32: '):-1])
2249
 
        num_entries_line = self._state_file.readline()
2250
 
        if not num_entries_line.startswith('num_entries: '):
2251
 
            raise errors.BzrError('missing num_entries line')
2252
 
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2253
 
 
2254
 
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
2255
 
        """Find a sha1 given a stat lookup."""
2256
 
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
2257
 
 
2258
 
    def _get_packed_stat_index(self):
2259
 
        """Get a packed_stat index of self._dirblocks."""
2260
 
        if self._packed_stat_index is None:
2261
 
            index = {}
2262
 
            for key, tree_details in self._iter_entries():
2263
 
                if tree_details[0][0] == 'f':
2264
 
                    index[tree_details[0][4]] = tree_details[0][1]
2265
 
            self._packed_stat_index = index
2266
 
        return self._packed_stat_index
2267
 
 
2268
 
    def save(self):
2269
 
        """Save any pending changes created during this session.
2270
 
 
2271
 
        We reuse the existing file, because that prevents race conditions with
2272
 
        file creation, and use oslocks on it to prevent concurrent modification
2273
 
        and reads - because dirstate's incremental data aggregation is not
2274
 
        compatible with reading a modified file, and replacing a file in use by
2275
 
        another process is impossible on Windows.
2276
 
 
2277
 
        A dirstate in read only mode should be smart enough though to validate
2278
 
        that the file has not changed, and otherwise discard its cache and
2279
 
        start over, to allow for fine grained read lock duration, so 'status'
2280
 
        wont block 'commit' - for example.
2281
 
        """
2282
 
        if self._changes_aborted:
2283
 
            # Should this be a warning? For now, I'm expecting that places that
2284
 
            # mark it inconsistent will warn, making a warning here redundant.
2285
 
            trace.mutter('Not saving DirState because '
2286
 
                    '_changes_aborted is set.')
2287
 
            return
2288
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2289
 
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2290
 
 
2291
 
            grabbed_write_lock = False
2292
 
            if self._lock_state != 'w':
2293
 
                grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
2294
 
                # Switch over to the new lock, as the old one may be closed.
2295
 
                # TODO: jam 20070315 We should validate the disk file has
2296
 
                #       not changed contents. Since temporary_write_lock may
2297
 
                #       not be an atomic operation.
2298
 
                self._lock_token = new_lock
2299
 
                self._state_file = new_lock.f
2300
 
                if not grabbed_write_lock:
2301
 
                    # We couldn't grab a write lock, so we switch back to a read one
2302
 
                    return
2303
 
            try:
2304
 
                self._state_file.seek(0)
2305
 
                self._state_file.writelines(self.get_lines())
2306
 
                self._state_file.truncate()
2307
 
                self._state_file.flush()
2308
 
                self._header_state = DirState.IN_MEMORY_UNMODIFIED
2309
 
                self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
2310
 
            finally:
2311
 
                if grabbed_write_lock:
2312
 
                    self._lock_token = self._lock_token.restore_read_lock()
2313
 
                    self._state_file = self._lock_token.f
2314
 
                    # TODO: jam 20070315 We should validate the disk file has
2315
 
                    #       not changed contents. Since restore_read_lock may
2316
 
                    #       not be an atomic operation.
2317
 
 
2318
 
    def _set_data(self, parent_ids, dirblocks):
2319
 
        """Set the full dirstate data in memory.
2320
 
 
2321
 
        This is an internal function used to completely replace the objects
2322
 
        in memory state. It puts the dirstate into state 'full-dirty'.
2323
 
 
2324
 
        :param parent_ids: A list of parent tree revision ids.
2325
 
        :param dirblocks: A list containing one tuple for each directory in the
2326
 
            tree. Each tuple contains the directory path and a list of entries
2327
 
            found in that directory.
2328
 
        """
2329
 
        # our memory copy is now authoritative.
2330
 
        self._dirblocks = dirblocks
2331
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2332
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2333
 
        self._parents = list(parent_ids)
2334
 
        self._id_index = None
2335
 
        self._packed_stat_index = None
2336
 
 
2337
 
    def set_path_id(self, path, new_id):
2338
 
        """Change the id of path to new_id in the current working tree.
2339
 
 
2340
 
        :param path: The path inside the tree to set - '' is the root, 'foo'
2341
 
            is the path foo in the root.
2342
 
        :param new_id: The new id to assign to the path. This must be a utf8
2343
 
            file id (not unicode, and not None).
2344
 
        """
2345
 
        self._read_dirblocks_if_needed()
2346
 
        if len(path):
2347
 
            # TODO: logic not written
2348
 
            raise NotImplementedError(self.set_path_id)
2349
 
        # TODO: check new id is unique
2350
 
        entry = self._get_entry(0, path_utf8=path)
2351
 
        if entry[0][2] == new_id:
2352
 
            # Nothing to change.
2353
 
            return
2354
 
        # mark the old path absent, and insert a new root path
2355
 
        self._make_absent(entry)
2356
 
        self.update_minimal(('', '', new_id), 'd',
2357
 
            path_utf8='', packed_stat=entry[1][0][4])
2358
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2359
 
 
2360
 
    def set_parent_trees(self, trees, ghosts):
2361
 
        """Set the parent trees for the dirstate.
2362
 
 
2363
 
        :param trees: A list of revision_id, tree tuples. tree must be provided
2364
 
            even if the revision_id refers to a ghost: supply an empty tree in
2365
 
            this case.
2366
 
        :param ghosts: A list of the revision_ids that are ghosts at the time
2367
 
            of setting.
2368
 
        """
2369
 
        # TODO: generate a list of parent indexes to preserve to save
2370
 
        # processing specific parent trees. In the common case one tree will
2371
 
        # be preserved - the left most parent.
2372
 
        # TODO: if the parent tree is a dirstate, we might want to walk them
2373
 
        # all by path in parallel for 'optimal' common-case performance.
2374
 
        # generate new root row.
2375
 
        self._read_dirblocks_if_needed()
2376
 
        # TODO future sketch: Examine the existing parents to generate a change
2377
 
        # map and then walk the new parent trees only, mapping them into the
2378
 
        # dirstate. Walk the dirstate at the same time to remove unreferenced
2379
 
        # entries.
2380
 
        # for now:
2381
 
        # sketch: loop over all entries in the dirstate, cherry picking
2382
 
        # entries from the parent trees, if they are not ghost trees.
2383
 
        # after we finish walking the dirstate, all entries not in the dirstate
2384
 
        # are deletes, so we want to append them to the end as per the design
2385
 
        # discussions. So do a set difference on ids with the parents to
2386
 
        # get deletes, and add them to the end.
2387
 
        # During the update process we need to answer the following questions:
2388
 
        # - find other keys containing a fileid in order to create cross-path
2389
 
        #   links. We dont't trivially use the inventory from other trees
2390
 
        #   because this leads to either double touching, or to accessing
2391
 
        #   missing keys,
2392
 
        # - find other keys containing a path
2393
 
        # We accumulate each entry via this dictionary, including the root
2394
 
        by_path = {}
2395
 
        id_index = {}
2396
 
        # we could do parallel iterators, but because file id data may be
2397
 
        # scattered throughout, we dont save on index overhead: we have to look
2398
 
        # at everything anyway. We can probably save cycles by reusing parent
2399
 
        # data and doing an incremental update when adding an additional
2400
 
        # parent, but for now the common cases are adding a new parent (merge),
2401
 
        # and replacing completely (commit), and commit is more common: so
2402
 
        # optimise merge later.
2403
 
 
2404
 
        # ---- start generation of full tree mapping data
2405
 
        # what trees should we use?
2406
 
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2407
 
        # how many trees do we end up with
2408
 
        parent_count = len(parent_trees)
2409
 
 
2410
 
        # one: the current tree
2411
 
        for entry in self._iter_entries():
2412
 
            # skip entries not in the current tree
2413
 
            if entry[1][0][0] in 'ar': # absent, relocated
2414
 
                continue
2415
 
            by_path[entry[0]] = [entry[1][0]] + \
2416
 
                [DirState.NULL_PARENT_DETAILS] * parent_count
2417
 
            id_index[entry[0][2]] = set([entry[0]])
2418
 
 
2419
 
        # now the parent trees:
2420
 
        for tree_index, tree in enumerate(parent_trees):
2421
 
            # the index is off by one, adjust it.
2422
 
            tree_index = tree_index + 1
2423
 
            # when we add new locations for a fileid we need these ranges for
2424
 
            # any fileid in this tree as we set the by_path[id] to:
2425
 
            # already_processed_tree_details + new_details + new_location_suffix
2426
 
            # the suffix is from tree_index+1:parent_count+1.
2427
 
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2428
 
            # now stitch in all the entries from this tree
2429
 
            for path, entry in tree.inventory.iter_entries_by_dir():
2430
 
                # here we process each trees details for each item in the tree.
2431
 
                # we first update any existing entries for the id at other paths,
2432
 
                # then we either create or update the entry for the id at the
2433
 
                # right path, and finally we add (if needed) a mapping from
2434
 
                # file_id to this path. We do it in this order to allow us to
2435
 
                # avoid checking all known paths for the id when generating a
2436
 
                # new entry at this path: by adding the id->path mapping last,
2437
 
                # all the mappings are valid and have correct relocation
2438
 
                # records where needed.
2439
 
                file_id = entry.file_id
2440
 
                path_utf8 = path.encode('utf8')
2441
 
                dirname, basename = osutils.split(path_utf8)
2442
 
                new_entry_key = (dirname, basename, file_id)
2443
 
                # tree index consistency: All other paths for this id in this tree
2444
 
                # index must point to the correct path.
2445
 
                for entry_key in id_index.setdefault(file_id, set()):
2446
 
                    # TODO:PROFILING: It might be faster to just update
2447
 
                    # rather than checking if we need to, and then overwrite
2448
 
                    # the one we are located at.
2449
 
                    if entry_key != new_entry_key:
2450
 
                        # this file id is at a different path in one of the
2451
 
                        # other trees, so put absent pointers there
2452
 
                        # This is the vertical axis in the matrix, all pointing
2453
 
                        # to the real path.
2454
 
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2455
 
                # by path consistency: Insert into an existing path record (trivial), or
2456
 
                # add a new one with relocation pointers for the other tree indexes.
2457
 
                if new_entry_key in id_index[file_id]:
2458
 
                    # there is already an entry where this data belongs, just insert it.
2459
 
                    by_path[new_entry_key][tree_index] = \
2460
 
                        self._inv_entry_to_details(entry)
2461
 
                else:
2462
 
                    # add relocated entries to the horizontal axis - this row
2463
 
                    # mapping from path,id. We need to look up the correct path
2464
 
                    # for the indexes from 0 to tree_index -1
2465
 
                    new_details = []
2466
 
                    for lookup_index in xrange(tree_index):
2467
 
                        # boundary case: this is the first occurence of file_id
2468
 
                        # so there are no id_indexs, possibly take this out of
2469
 
                        # the loop?
2470
 
                        if not len(id_index[file_id]):
2471
 
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2472
 
                        else:
2473
 
                            # grab any one entry, use it to find the right path.
2474
 
                            # TODO: optimise this to reduce memory use in highly
2475
 
                            # fragmented situations by reusing the relocation
2476
 
                            # records.
2477
 
                            a_key = iter(id_index[file_id]).next()
2478
 
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2479
 
                                # its a pointer or missing statement, use it as is.
2480
 
                                new_details.append(by_path[a_key][lookup_index])
2481
 
                            else:
2482
 
                                # we have the right key, make a pointer to it.
2483
 
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2484
 
                                new_details.append(('r', real_path, 0, False, ''))
2485
 
                    new_details.append(self._inv_entry_to_details(entry))
2486
 
                    new_details.extend(new_location_suffix)
2487
 
                    by_path[new_entry_key] = new_details
2488
 
                    id_index[file_id].add(new_entry_key)
2489
 
        # --- end generation of full tree mappings
2490
 
 
2491
 
        # sort and output all the entries
2492
 
        new_entries = self._sort_entries(by_path.items())
2493
 
        self._entries_to_current_state(new_entries)
2494
 
        self._parents = [rev_id for rev_id, tree in trees]
2495
 
        self._ghosts = list(ghosts)
2496
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2497
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2498
 
        self._id_index = id_index
2499
 
 
2500
 
    def _sort_entries(self, entry_list):
2501
 
        """Given a list of entries, sort them into the right order.
2502
 
 
2503
 
        This is done when constructing a new dirstate from trees - normally we
2504
 
        try to keep everything in sorted blocks all the time, but sometimes
2505
 
        it's easier to sort after the fact.
2506
 
        """
2507
 
        def _key(entry):
2508
 
            # sort by: directory parts, file name, file id
2509
 
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
2510
 
        return sorted(entry_list, key=_key)
2511
 
 
2512
 
    def set_state_from_inventory(self, new_inv):
2513
 
        """Set new_inv as the current state.
2514
 
 
2515
 
        This API is called by tree transform, and will usually occur with
2516
 
        existing parent trees.
2517
 
 
2518
 
        :param new_inv: The inventory object to set current state from.
2519
 
        """
2520
 
        if 'evil' in debug.debug_flags:
2521
 
            trace.mutter_callsite(1,
2522
 
                "set_state_from_inventory called; please mutate the tree instead")
2523
 
        tracing = 'dirstate' in debug.debug_flags
2524
 
        if tracing:
2525
 
            trace.mutter("set_state_from_inventory trace:")
2526
 
        self._read_dirblocks_if_needed()
2527
 
        # sketch:
2528
 
        # Two iterators: current data and new data, both in dirblock order.
2529
 
        # We zip them together, which tells about entries that are new in the
2530
 
        # inventory, or removed in the inventory, or present in both and
2531
 
        # possibly changed.
2532
 
        #
2533
 
        # You might think we could just synthesize a new dirstate directly
2534
 
        # since we're processing it in the right order.  However, we need to
2535
 
        # also consider there may be any number of parent trees and relocation
2536
 
        # pointers, and we don't want to duplicate that here.
2537
 
        new_iterator = new_inv.iter_entries_by_dir()
2538
 
        # we will be modifying the dirstate, so we need a stable iterator. In
2539
 
        # future we might write one, for now we just clone the state into a
2540
 
        # list using a copy so that we see every original item and don't have
2541
 
        # to adjust the position when items are inserted or deleted in the
2542
 
        # underlying dirstate.
2543
 
        old_iterator = iter(list(self._iter_entries()))
2544
 
        # both must have roots so this is safe:
2545
 
        current_new = new_iterator.next()
2546
 
        current_old = old_iterator.next()
2547
 
        def advance(iterator):
2548
 
            try:
2549
 
                return iterator.next()
2550
 
            except StopIteration:
2551
 
                return None
2552
 
        while current_new or current_old:
2553
 
            # skip entries in old that are not really there
2554
 
            if current_old and current_old[1][0][0] in 'ar':
2555
 
                # relocated or absent
2556
 
                current_old = advance(old_iterator)
2557
 
                continue
2558
 
            if current_new:
2559
 
                # convert new into dirblock style
2560
 
                new_path_utf8 = current_new[0].encode('utf8')
2561
 
                new_dirname, new_basename = osutils.split(new_path_utf8)
2562
 
                new_id = current_new[1].file_id
2563
 
                new_entry_key = (new_dirname, new_basename, new_id)
2564
 
                current_new_minikind = \
2565
 
                    DirState._kind_to_minikind[current_new[1].kind]
2566
 
                if current_new_minikind == 't':
2567
 
                    fingerprint = current_new[1].reference_revision or ''
2568
 
                else:
2569
 
                    # We normally only insert or remove records, or update
2570
 
                    # them when it has significantly changed.  Then we want to
2571
 
                    # erase its fingerprint.  Unaffected records should
2572
 
                    # normally not be updated at all.
2573
 
                    fingerprint = ''
2574
 
            else:
2575
 
                # for safety disable variables
2576
 
                new_path_utf8 = new_dirname = new_basename = new_id = \
2577
 
                    new_entry_key = None
2578
 
            # 5 cases, we dont have a value that is strictly greater than everything, so
2579
 
            # we make both end conditions explicit
2580
 
            if not current_old:
2581
 
                # old is finished: insert current_new into the state.
2582
 
                if tracing:
2583
 
                    trace.mutter("Appending from new '%s'.",
2584
 
                        new_path_utf8.decode('utf8'))
2585
 
                self.update_minimal(new_entry_key, current_new_minikind,
2586
 
                    executable=current_new[1].executable,
2587
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
2588
 
                    fullscan=True)
2589
 
                current_new = advance(new_iterator)
2590
 
            elif not current_new:
2591
 
                # new is finished
2592
 
                if tracing:
2593
 
                    trace.mutter("Truncating from old '%s/%s'.",
2594
 
                        current_old[0][0].decode('utf8'),
2595
 
                        current_old[0][1].decode('utf8'))
2596
 
                self._make_absent(current_old)
2597
 
                current_old = advance(old_iterator)
2598
 
            elif new_entry_key == current_old[0]:
2599
 
                # same -  common case
2600
 
                # We're looking at the same path and id in both the dirstate
2601
 
                # and inventory, so just need to update the fields in the
2602
 
                # dirstate from the one in the inventory.
2603
 
                # TODO: update the record if anything significant has changed.
2604
 
                # the minimal required trigger is if the execute bit or cached
2605
 
                # kind has changed.
2606
 
                if (current_old[1][0][3] != current_new[1].executable or
2607
 
                    current_old[1][0][0] != current_new_minikind):
2608
 
                    if tracing:
2609
 
                        trace.mutter("Updating in-place change '%s'.",
2610
 
                            new_path_utf8.decode('utf8'))
2611
 
                    self.update_minimal(current_old[0], current_new_minikind,
2612
 
                        executable=current_new[1].executable,
2613
 
                        path_utf8=new_path_utf8, fingerprint=fingerprint,
2614
 
                        fullscan=True)
2615
 
                # both sides are dealt with, move on
2616
 
                current_old = advance(old_iterator)
2617
 
                current_new = advance(new_iterator)
2618
 
            elif (cmp_by_dirs(new_dirname, current_old[0][0]) < 0
2619
 
                  or (new_dirname == current_old[0][0]
2620
 
                      and new_entry_key[1:] < current_old[0][1:])):
2621
 
                # new comes before:
2622
 
                # add a entry for this and advance new
2623
 
                if tracing:
2624
 
                    trace.mutter("Inserting from new '%s'.",
2625
 
                        new_path_utf8.decode('utf8'))
2626
 
                self.update_minimal(new_entry_key, current_new_minikind,
2627
 
                    executable=current_new[1].executable,
2628
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
2629
 
                    fullscan=True)
2630
 
                current_new = advance(new_iterator)
2631
 
            else:
2632
 
                # we've advanced past the place where the old key would be,
2633
 
                # without seeing it in the new list.  so it must be gone.
2634
 
                if tracing:
2635
 
                    trace.mutter("Deleting from old '%s/%s'.",
2636
 
                        current_old[0][0].decode('utf8'),
2637
 
                        current_old[0][1].decode('utf8'))
2638
 
                self._make_absent(current_old)
2639
 
                current_old = advance(old_iterator)
2640
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2641
 
        self._id_index = None
2642
 
        self._packed_stat_index = None
2643
 
        if tracing:
2644
 
            trace.mutter("set_state_from_inventory complete.")
2645
 
 
2646
 
    def _make_absent(self, current_old):
2647
 
        """Mark current_old - an entry - as absent for tree 0.
2648
 
 
2649
 
        :return: True if this was the last details entry for the entry key:
2650
 
            that is, if the underlying block has had the entry removed, thus
2651
 
            shrinking in length.
2652
 
        """
2653
 
        # build up paths that this id will be left at after the change is made,
2654
 
        # so we can update their cross references in tree 0
2655
 
        all_remaining_keys = set()
2656
 
        # Dont check the working tree, because it's going.
2657
 
        for details in current_old[1][1:]:
2658
 
            if details[0] not in 'ar': # absent, relocated
2659
 
                all_remaining_keys.add(current_old[0])
2660
 
            elif details[0] == 'r': # relocated
2661
 
                # record the key for the real path.
2662
 
                all_remaining_keys.add(tuple(osutils.split(details[1])) + (current_old[0][2],))
2663
 
            # absent rows are not present at any path.
2664
 
        last_reference = current_old[0] not in all_remaining_keys
2665
 
        if last_reference:
2666
 
            # the current row consists entire of the current item (being marked
2667
 
            # absent), and relocated or absent entries for the other trees:
2668
 
            # Remove it, its meaningless.
2669
 
            block = self._find_block(current_old[0])
2670
 
            entry_index, present = self._find_entry_index(current_old[0], block[1])
2671
 
            if not present:
2672
 
                raise AssertionError('could not find entry for %s' % (current_old,))
2673
 
            block[1].pop(entry_index)
2674
 
            # if we have an id_index in use, remove this key from it for this id.
2675
 
            if self._id_index is not None:
2676
 
                self._id_index[current_old[0][2]].remove(current_old[0])
2677
 
        # update all remaining keys for this id to record it as absent. The
2678
 
        # existing details may either be the record we are marking as deleted
2679
 
        # (if there were other trees with the id present at this path), or may
2680
 
        # be relocations.
2681
 
        for update_key in all_remaining_keys:
2682
 
            update_block_index, present = \
2683
 
                self._find_block_index_from_key(update_key)
2684
 
            if not present:
2685
 
                raise AssertionError('could not find block for %s' % (update_key,))
2686
 
            update_entry_index, present = \
2687
 
                self._find_entry_index(update_key, self._dirblocks[update_block_index][1])
2688
 
            if not present:
2689
 
                raise AssertionError('could not find entry for %s' % (update_key,))
2690
 
            update_tree_details = self._dirblocks[update_block_index][1][update_entry_index][1]
2691
 
            # it must not be absent at the moment
2692
 
            if update_tree_details[0][0] == 'a': # absent
2693
 
                raise AssertionError('bad row %r' % (update_tree_details,))
2694
 
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2695
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2696
 
        return last_reference
2697
 
 
2698
 
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2699
 
        packed_stat=None, size=0, path_utf8=None, fullscan=False):
2700
 
        """Update an entry to the state in tree 0.
2701
 
 
2702
 
        This will either create a new entry at 'key' or update an existing one.
2703
 
        It also makes sure that any other records which might mention this are
2704
 
        updated as well.
2705
 
 
2706
 
        :param key: (dir, name, file_id) for the new entry
2707
 
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
2708
 
                'directory'), etc.
2709
 
        :param executable: Should the executable bit be set?
2710
 
        :param fingerprint: Simple fingerprint for new entry: canonical-form
2711
 
            sha1 for files, referenced revision id for subtrees, etc.
2712
 
        :param packed_stat: Packed stat value for new entry.
2713
 
        :param size: Size information for new entry
2714
 
        :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
2715
 
                extra computation.
2716
 
        :param fullscan: If True then a complete scan of the dirstate is being
2717
 
            done and checking for duplicate rows should not be done. This
2718
 
            should only be set by set_state_from_inventory and similar methods.
2719
 
 
2720
 
        If packed_stat and fingerprint are not given, they're invalidated in
2721
 
        the entry.
2722
 
        """
2723
 
        block = self._find_block(key)[1]
2724
 
        if packed_stat is None:
2725
 
            packed_stat = DirState.NULLSTAT
2726
 
        # XXX: Some callers pass '' as the packed_stat, and it seems to be
2727
 
        # sometimes present in the dirstate - this seems oddly inconsistent.
2728
 
        # mbp 20071008
2729
 
        entry_index, present = self._find_entry_index(key, block)
2730
 
        new_details = (minikind, fingerprint, size, executable, packed_stat)
2731
 
        id_index = self._get_id_index()
2732
 
        if not present:
2733
 
            # New record. Check there isn't a entry at this path already.
2734
 
            if not fullscan:
2735
 
                low_index, _ = self._find_entry_index(key[0:2] + ('',), block)
2736
 
                while low_index < len(block):
2737
 
                    entry = block[low_index]
2738
 
                    if entry[0][0:2] == key[0:2]:
2739
 
                        if entry[1][0][0] not in 'ar':
2740
 
                            # This entry has the same path (but a different id) as
2741
 
                            # the new entry we're adding, and is present in ths
2742
 
                            # tree.
2743
 
                            raise errors.InconsistentDelta(
2744
 
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2745
 
                                "Attempt to add item at path already occupied by "
2746
 
                                "id %r" % entry[0][2])
2747
 
                        low_index += 1
2748
 
                    else:
2749
 
                        break
2750
 
            # new entry, synthesis cross reference here,
2751
 
            existing_keys = id_index.setdefault(key[2], set())
2752
 
            if not existing_keys:
2753
 
                # not currently in the state, simplest case
2754
 
                new_entry = key, [new_details] + self._empty_parent_info()
2755
 
            else:
2756
 
                # present at one or more existing other paths.
2757
 
                # grab one of them and use it to generate parent
2758
 
                # relocation/absent entries.
2759
 
                new_entry = key, [new_details]
2760
 
                # existing_keys can be changed as we iterate.
2761
 
                for other_key in tuple(existing_keys):
2762
 
                    # change the record at other to be a pointer to this new
2763
 
                    # record. The loop looks similar to the change to
2764
 
                    # relocations when updating an existing record but its not:
2765
 
                    # the test for existing kinds is different: this can be
2766
 
                    # factored out to a helper though.
2767
 
                    other_block_index, present = self._find_block_index_from_key(
2768
 
                        other_key)
2769
 
                    if not present:
2770
 
                        raise AssertionError('could not find block for %s' % (
2771
 
                            other_key,))
2772
 
                    other_block = self._dirblocks[other_block_index][1]
2773
 
                    other_entry_index, present = self._find_entry_index(
2774
 
                        other_key, other_block)
2775
 
                    if not present:
2776
 
                        raise AssertionError(
2777
 
                            'update_minimal: could not find other entry for %s'
2778
 
                            % (other_key,))
2779
 
                    if path_utf8 is None:
2780
 
                        raise AssertionError('no path')
2781
 
                    # Turn this other location into a reference to the new
2782
 
                    # location. This also updates the aliased iterator
2783
 
                    # (current_old in set_state_from_inventory) so that the old
2784
 
                    # entry, if not already examined, is skipped over by that
2785
 
                    # loop.
2786
 
                    other_entry = other_block[other_entry_index]
2787
 
                    other_entry[1][0] = ('r', path_utf8, 0, False, '')
2788
 
                    self._maybe_remove_row(other_block, other_entry_index,
2789
 
                        id_index)
2790
 
 
2791
 
                # This loop:
2792
 
                # adds a tuple to the new details for each column
2793
 
                #  - either by copying an existing relocation pointer inside that column
2794
 
                #  - or by creating a new pointer to the right row inside that column
2795
 
                num_present_parents = self._num_present_parents()
2796
 
                if num_present_parents:
2797
 
                    other_key = list(existing_keys)[0]
2798
 
                for lookup_index in xrange(1, num_present_parents + 1):
2799
 
                    # grab any one entry, use it to find the right path.
2800
 
                    # TODO: optimise this to reduce memory use in highly
2801
 
                    # fragmented situations by reusing the relocation
2802
 
                    # records.
2803
 
                    update_block_index, present = \
2804
 
                        self._find_block_index_from_key(other_key)
2805
 
                    if not present:
2806
 
                        raise AssertionError('could not find block for %s' % (other_key,))
2807
 
                    update_entry_index, present = \
2808
 
                        self._find_entry_index(other_key, self._dirblocks[update_block_index][1])
2809
 
                    if not present:
2810
 
                        raise AssertionError('update_minimal: could not find entry for %s' % (other_key,))
2811
 
                    update_details = self._dirblocks[update_block_index][1][update_entry_index][1][lookup_index]
2812
 
                    if update_details[0] in 'ar': # relocated, absent
2813
 
                        # its a pointer or absent in lookup_index's tree, use
2814
 
                        # it as is.
2815
 
                        new_entry[1].append(update_details)
2816
 
                    else:
2817
 
                        # we have the right key, make a pointer to it.
2818
 
                        pointer_path = osutils.pathjoin(*other_key[0:2])
2819
 
                        new_entry[1].append(('r', pointer_path, 0, False, ''))
2820
 
            block.insert(entry_index, new_entry)
2821
 
            existing_keys.add(key)
2822
 
        else:
2823
 
            # Does the new state matter?
2824
 
            block[entry_index][1][0] = new_details
2825
 
            # parents cannot be affected by what we do.
2826
 
            # other occurences of this id can be found
2827
 
            # from the id index.
2828
 
            # ---
2829
 
            # tree index consistency: All other paths for this id in this tree
2830
 
            # index must point to the correct path. We have to loop here because
2831
 
            # we may have passed entries in the state with this file id already
2832
 
            # that were absent - where parent entries are - and they need to be
2833
 
            # converted to relocated.
2834
 
            if path_utf8 is None:
2835
 
                raise AssertionError('no path')
2836
 
            for entry_key in id_index.setdefault(key[2], set()):
2837
 
                # TODO:PROFILING: It might be faster to just update
2838
 
                # rather than checking if we need to, and then overwrite
2839
 
                # the one we are located at.
2840
 
                if entry_key != key:
2841
 
                    # this file id is at a different path in one of the
2842
 
                    # other trees, so put absent pointers there
2843
 
                    # This is the vertical axis in the matrix, all pointing
2844
 
                    # to the real path.
2845
 
                    block_index, present = self._find_block_index_from_key(entry_key)
2846
 
                    if not present:
2847
 
                        raise AssertionError('not present: %r', entry_key)
2848
 
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
2849
 
                    if not present:
2850
 
                        raise AssertionError('not present: %r', entry_key)
2851
 
                    self._dirblocks[block_index][1][entry_index][1][0] = \
2852
 
                        ('r', path_utf8, 0, False, '')
2853
 
        # add a containing dirblock if needed.
2854
 
        if new_details[0] == 'd':
2855
 
            subdir_key = (osutils.pathjoin(*key[0:2]), '', '')
2856
 
            block_index, present = self._find_block_index_from_key(subdir_key)
2857
 
            if not present:
2858
 
                self._dirblocks.insert(block_index, (subdir_key[0], []))
2859
 
 
2860
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2861
 
 
2862
 
    def _maybe_remove_row(self, block, index, id_index):
2863
 
        """Remove index if it is absent or relocated across the row.
2864
 
        
2865
 
        id_index is updated accordingly.
2866
 
        """
2867
 
        present_in_row = False
2868
 
        entry = block[index]
2869
 
        for column in entry[1]:
2870
 
            if column[0] not in 'ar':
2871
 
                present_in_row = True
2872
 
                break
2873
 
        if not present_in_row:
2874
 
            block.pop(index)
2875
 
            id_index[entry[0][2]].remove(entry[0])
2876
 
 
2877
 
    def _validate(self):
2878
 
        """Check that invariants on the dirblock are correct.
2879
 
 
2880
 
        This can be useful in debugging; it shouldn't be necessary in
2881
 
        normal code.
2882
 
 
2883
 
        This must be called with a lock held.
2884
 
        """
2885
 
        # NOTE: This must always raise AssertionError not just assert,
2886
 
        # otherwise it may not behave properly under python -O
2887
 
        #
2888
 
        # TODO: All entries must have some content that's not 'a' or 'r',
2889
 
        # otherwise it could just be removed.
2890
 
        #
2891
 
        # TODO: All relocations must point directly to a real entry.
2892
 
        #
2893
 
        # TODO: No repeated keys.
2894
 
        #
2895
 
        # -- mbp 20070325
2896
 
        from pprint import pformat
2897
 
        self._read_dirblocks_if_needed()
2898
 
        if len(self._dirblocks) > 0:
2899
 
            if not self._dirblocks[0][0] == '':
2900
 
                raise AssertionError(
2901
 
                    "dirblocks don't start with root block:\n" + \
2902
 
                    pformat(self._dirblocks))
2903
 
        if len(self._dirblocks) > 1:
2904
 
            if not self._dirblocks[1][0] == '':
2905
 
                raise AssertionError(
2906
 
                    "dirblocks missing root directory:\n" + \
2907
 
                    pformat(self._dirblocks))
2908
 
        # the dirblocks are sorted by their path components, name, and dir id
2909
 
        dir_names = [d[0].split('/')
2910
 
                for d in self._dirblocks[1:]]
2911
 
        if dir_names != sorted(dir_names):
2912
 
            raise AssertionError(
2913
 
                "dir names are not in sorted order:\n" + \
2914
 
                pformat(self._dirblocks) + \
2915
 
                "\nkeys:\n" +
2916
 
                pformat(dir_names))
2917
 
        for dirblock in self._dirblocks:
2918
 
            # within each dirblock, the entries are sorted by filename and
2919
 
            # then by id.
2920
 
            for entry in dirblock[1]:
2921
 
                if dirblock[0] != entry[0][0]:
2922
 
                    raise AssertionError(
2923
 
                        "entry key for %r"
2924
 
                        "doesn't match directory name in\n%r" %
2925
 
                        (entry, pformat(dirblock)))
2926
 
            if dirblock[1] != sorted(dirblock[1]):
2927
 
                raise AssertionError(
2928
 
                    "dirblock for %r is not sorted:\n%s" % \
2929
 
                    (dirblock[0], pformat(dirblock)))
2930
 
 
2931
 
        def check_valid_parent():
2932
 
            """Check that the current entry has a valid parent.
2933
 
 
2934
 
            This makes sure that the parent has a record,
2935
 
            and that the parent isn't marked as "absent" in the
2936
 
            current tree. (It is invalid to have a non-absent file in an absent
2937
 
            directory.)
2938
 
            """
2939
 
            if entry[0][0:2] == ('', ''):
2940
 
                # There should be no parent for the root row
2941
 
                return
2942
 
            parent_entry = self._get_entry(tree_index, path_utf8=entry[0][0])
2943
 
            if parent_entry == (None, None):
2944
 
                raise AssertionError(
2945
 
                    "no parent entry for: %s in tree %s"
2946
 
                    % (this_path, tree_index))
2947
 
            if parent_entry[1][tree_index][0] != 'd':
2948
 
                raise AssertionError(
2949
 
                    "Parent entry for %s is not marked as a valid"
2950
 
                    " directory. %s" % (this_path, parent_entry,))
2951
 
 
2952
 
        # For each file id, for each tree: either
2953
 
        # the file id is not present at all; all rows with that id in the
2954
 
        # key have it marked as 'absent'
2955
 
        # OR the file id is present under exactly one name; any other entries
2956
 
        # that mention that id point to the correct name.
2957
 
        #
2958
 
        # We check this with a dict per tree pointing either to the present
2959
 
        # name, or None if absent.
2960
 
        tree_count = self._num_present_parents() + 1
2961
 
        id_path_maps = [dict() for i in range(tree_count)]
2962
 
        # Make sure that all renamed entries point to the correct location.
2963
 
        for entry in self._iter_entries():
2964
 
            file_id = entry[0][2]
2965
 
            this_path = osutils.pathjoin(entry[0][0], entry[0][1])
2966
 
            if len(entry[1]) != tree_count:
2967
 
                raise AssertionError(
2968
 
                "wrong number of entry details for row\n%s" \
2969
 
                ",\nexpected %d" % \
2970
 
                (pformat(entry), tree_count))
2971
 
            absent_positions = 0
2972
 
            for tree_index, tree_state in enumerate(entry[1]):
2973
 
                this_tree_map = id_path_maps[tree_index]
2974
 
                minikind = tree_state[0]
2975
 
                if minikind in 'ar':
2976
 
                    absent_positions += 1
2977
 
                # have we seen this id before in this column?
2978
 
                if file_id in this_tree_map:
2979
 
                    previous_path, previous_loc = this_tree_map[file_id]
2980
 
                    # any later mention of this file must be consistent with
2981
 
                    # what was said before
2982
 
                    if minikind == 'a':
2983
 
                        if previous_path is not None:
2984
 
                            raise AssertionError(
2985
 
                            "file %s is absent in row %r but also present " \
2986
 
                            "at %r"% \
2987
 
                            (file_id, entry, previous_path))
2988
 
                    elif minikind == 'r':
2989
 
                        target_location = tree_state[1]
2990
 
                        if previous_path != target_location:
2991
 
                            raise AssertionError(
2992
 
                            "file %s relocation in row %r but also at %r" \
2993
 
                            % (file_id, entry, previous_path))
2994
 
                    else:
2995
 
                        # a file, directory, etc - may have been previously
2996
 
                        # pointed to by a relocation, which must point here
2997
 
                        if previous_path != this_path:
2998
 
                            raise AssertionError(
2999
 
                                "entry %r inconsistent with previous path %r "
3000
 
                                "seen at %r" %
3001
 
                                (entry, previous_path, previous_loc))
3002
 
                        check_valid_parent()
3003
 
                else:
3004
 
                    if minikind == 'a':
3005
 
                        # absent; should not occur anywhere else
3006
 
                        this_tree_map[file_id] = None, this_path
3007
 
                    elif minikind == 'r':
3008
 
                        # relocation, must occur at expected location
3009
 
                        this_tree_map[file_id] = tree_state[1], this_path
3010
 
                    else:
3011
 
                        this_tree_map[file_id] = this_path, this_path
3012
 
                        check_valid_parent()
3013
 
            if absent_positions == tree_count:
3014
 
                raise AssertionError(
3015
 
                    "entry %r has no data for any tree." % (entry,))
3016
 
        if self._id_index is not None:
3017
 
            for file_id, entry_keys in self._id_index.iteritems():
3018
 
                for entry_key in entry_keys:
3019
 
                    if entry_key[2] != file_id:
3020
 
                        raise AssertionError(
3021
 
                            'file_id %r did not match entry key %s'
3022
 
                            % (file_id, entry_key))
3023
 
 
3024
 
    def _wipe_state(self):
3025
 
        """Forget all state information about the dirstate."""
3026
 
        self._header_state = DirState.NOT_IN_MEMORY
3027
 
        self._dirblock_state = DirState.NOT_IN_MEMORY
3028
 
        self._changes_aborted = False
3029
 
        self._parents = []
3030
 
        self._ghosts = []
3031
 
        self._dirblocks = []
3032
 
        self._id_index = None
3033
 
        self._packed_stat_index = None
3034
 
        self._end_of_header = None
3035
 
        self._cutoff_time = None
3036
 
        self._split_path_cache = {}
3037
 
 
3038
 
    def lock_read(self):
3039
 
        """Acquire a read lock on the dirstate."""
3040
 
        if self._lock_token is not None:
3041
 
            raise errors.LockContention(self._lock_token)
3042
 
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
3043
 
        #       already in memory, we could read just the header and check for
3044
 
        #       any modification. If not modified, we can just leave things
3045
 
        #       alone
3046
 
        self._lock_token = lock.ReadLock(self._filename)
3047
 
        self._lock_state = 'r'
3048
 
        self._state_file = self._lock_token.f
3049
 
        self._wipe_state()
3050
 
 
3051
 
    def lock_write(self):
3052
 
        """Acquire a write lock on the dirstate."""
3053
 
        if self._lock_token is not None:
3054
 
            raise errors.LockContention(self._lock_token)
3055
 
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
3056
 
        #       already in memory, we could read just the header and check for
3057
 
        #       any modification. If not modified, we can just leave things
3058
 
        #       alone
3059
 
        self._lock_token = lock.WriteLock(self._filename)
3060
 
        self._lock_state = 'w'
3061
 
        self._state_file = self._lock_token.f
3062
 
        self._wipe_state()
3063
 
 
3064
 
    def unlock(self):
3065
 
        """Drop any locks held on the dirstate."""
3066
 
        if self._lock_token is None:
3067
 
            raise errors.LockNotHeld(self)
3068
 
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
3069
 
        #       already in memory, we could read just the header and check for
3070
 
        #       any modification. If not modified, we can just leave things
3071
 
        #       alone
3072
 
        self._state_file = None
3073
 
        self._lock_state = None
3074
 
        self._lock_token.unlock()
3075
 
        self._lock_token = None
3076
 
        self._split_path_cache = {}
3077
 
 
3078
 
    def _requires_lock(self):
3079
 
        """Check that a lock is currently held by someone on the dirstate."""
3080
 
        if not self._lock_token:
3081
 
            raise errors.ObjectNotLocked(self)
3082
 
 
3083
 
 
3084
 
def py_update_entry(state, entry, abspath, stat_value,
3085
 
                 _stat_to_minikind=DirState._stat_to_minikind,
3086
 
                 _pack_stat=pack_stat):
3087
 
    """Update the entry based on what is actually on disk.
3088
 
 
3089
 
    This function only calculates the sha if it needs to - if the entry is
3090
 
    uncachable, or clearly different to the first parent's entry, no sha
3091
 
    is calculated, and None is returned.
3092
 
 
3093
 
    :param state: The dirstate this entry is in.
3094
 
    :param entry: This is the dirblock entry for the file in question.
3095
 
    :param abspath: The path on disk for this file.
3096
 
    :param stat_value: The stat value done on the path.
3097
 
    :return: None, or The sha1 hexdigest of the file (40 bytes) or link
3098
 
        target of a symlink.
3099
 
    """
3100
 
    try:
3101
 
        minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
3102
 
    except KeyError:
3103
 
        # Unhandled kind
3104
 
        return None
3105
 
    packed_stat = _pack_stat(stat_value)
3106
 
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3107
 
     saved_executable, saved_packed_stat) = entry[1][0]
3108
 
 
3109
 
    if minikind == 'd' and saved_minikind == 't':
3110
 
        minikind = 't'
3111
 
    if (minikind == saved_minikind
3112
 
        and packed_stat == saved_packed_stat):
3113
 
        # The stat hasn't changed since we saved, so we can re-use the
3114
 
        # saved sha hash.
3115
 
        if minikind == 'd':
3116
 
            return None
3117
 
 
3118
 
        # size should also be in packed_stat
3119
 
        if saved_file_size == stat_value.st_size:
3120
 
            return saved_link_or_sha1
3121
 
 
3122
 
    # If we have gotten this far, that means that we need to actually
3123
 
    # process this entry.
3124
 
    link_or_sha1 = None
3125
 
    if minikind == 'f':
3126
 
        executable = state._is_executable(stat_value.st_mode,
3127
 
                                         saved_executable)
3128
 
        if state._cutoff_time is None:
3129
 
            state._sha_cutoff_time()
3130
 
        if (stat_value.st_mtime < state._cutoff_time
3131
 
            and stat_value.st_ctime < state._cutoff_time
3132
 
            and len(entry[1]) > 1
3133
 
            and entry[1][1][0] != 'a'):
3134
 
            # Could check for size changes for further optimised
3135
 
            # avoidance of sha1's. However the most prominent case of
3136
 
            # over-shaing is during initial add, which this catches.
3137
 
            # Besides, if content filtering happens, size and sha
3138
 
            # are calculated at the same time, so checking just the size
3139
 
            # gains nothing w.r.t. performance.
3140
 
            link_or_sha1 = state._sha1_file(abspath)
3141
 
            entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
3142
 
                           executable, packed_stat)
3143
 
        else:
3144
 
            entry[1][0] = ('f', '', stat_value.st_size,
3145
 
                           executable, DirState.NULLSTAT)
3146
 
    elif minikind == 'd':
3147
 
        link_or_sha1 = None
3148
 
        entry[1][0] = ('d', '', 0, False, packed_stat)
3149
 
        if saved_minikind != 'd':
3150
 
            # This changed from something into a directory. Make sure we
3151
 
            # have a directory block for it. This doesn't happen very
3152
 
            # often, so this doesn't have to be super fast.
3153
 
            block_index, entry_index, dir_present, file_present = \
3154
 
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3155
 
            state._ensure_block(block_index, entry_index,
3156
 
                               osutils.pathjoin(entry[0][0], entry[0][1]))
3157
 
    elif minikind == 'l':
3158
 
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3159
 
        if state._cutoff_time is None:
3160
 
            state._sha_cutoff_time()
3161
 
        if (stat_value.st_mtime < state._cutoff_time
3162
 
            and stat_value.st_ctime < state._cutoff_time):
3163
 
            entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
3164
 
                           False, packed_stat)
3165
 
        else:
3166
 
            entry[1][0] = ('l', '', stat_value.st_size,
3167
 
                           False, DirState.NULLSTAT)
3168
 
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
3169
 
    return link_or_sha1
3170
 
 
3171
 
 
3172
 
class ProcessEntryPython(object):
3173
 
 
3174
 
    __slots__ = ["old_dirname_to_file_id", "new_dirname_to_file_id",
3175
 
        "last_source_parent", "last_target_parent", "include_unchanged",
3176
 
        "partial", "use_filesystem_for_exec", "utf8_decode",
3177
 
        "searched_specific_files", "search_specific_files",
3178
 
        "searched_exact_paths", "search_specific_file_parents", "seen_ids",
3179
 
        "state", "source_index", "target_index", "want_unversioned", "tree"]
3180
 
 
3181
 
    def __init__(self, include_unchanged, use_filesystem_for_exec,
3182
 
        search_specific_files, state, source_index, target_index,
3183
 
        want_unversioned, tree):
3184
 
        self.old_dirname_to_file_id = {}
3185
 
        self.new_dirname_to_file_id = {}
3186
 
        # Are we doing a partial iter_changes?
3187
 
        self.partial = search_specific_files != set([''])
3188
 
        # Using a list so that we can access the values and change them in
3189
 
        # nested scope. Each one is [path, file_id, entry]
3190
 
        self.last_source_parent = [None, None]
3191
 
        self.last_target_parent = [None, None]
3192
 
        self.include_unchanged = include_unchanged
3193
 
        self.use_filesystem_for_exec = use_filesystem_for_exec
3194
 
        self.utf8_decode = cache_utf8._utf8_decode
3195
 
        # for all search_indexs in each path at or under each element of
3196
 
        # search_specific_files, if the detail is relocated: add the id, and
3197
 
        # add the relocated path as one to search if its not searched already.
3198
 
        # If the detail is not relocated, add the id.
3199
 
        self.searched_specific_files = set()
3200
 
        # When we search exact paths without expanding downwards, we record
3201
 
        # that here.
3202
 
        self.searched_exact_paths = set()
3203
 
        self.search_specific_files = search_specific_files
3204
 
        # The parents up to the root of the paths we are searching.
3205
 
        # After all normal paths are returned, these specific items are returned.
3206
 
        self.search_specific_file_parents = set()
3207
 
        # The ids we've sent out in the delta.
3208
 
        self.seen_ids = set()
3209
 
        self.state = state
3210
 
        self.source_index = source_index
3211
 
        self.target_index = target_index
3212
 
        if target_index != 0:
3213
 
            # A lot of code in here depends on target_index == 0
3214
 
            raise errors.BzrError('unsupported target index')
3215
 
        self.want_unversioned = want_unversioned
3216
 
        self.tree = tree
3217
 
 
3218
 
    def _process_entry(self, entry, path_info, pathjoin=osutils.pathjoin):
3219
 
        """Compare an entry and real disk to generate delta information.
3220
 
 
3221
 
        :param path_info: top_relpath, basename, kind, lstat, abspath for
3222
 
            the path of entry. If None, then the path is considered absent in 
3223
 
            the target (Perhaps we should pass in a concrete entry for this ?)
3224
 
            Basename is returned as a utf8 string because we expect this
3225
 
            tuple will be ignored, and don't want to take the time to
3226
 
            decode.
3227
 
        :return: (iter_changes_result, changed). If the entry has not been
3228
 
            handled then changed is None. Otherwise it is False if no content
3229
 
            or metadata changes have occurred, and True if any content or
3230
 
            metadata change has occurred. If self.include_unchanged is True then
3231
 
            if changed is not None, iter_changes_result will always be a result
3232
 
            tuple. Otherwise, iter_changes_result is None unless changed is
3233
 
            True.
3234
 
        """
3235
 
        if self.source_index is None:
3236
 
            source_details = DirState.NULL_PARENT_DETAILS
3237
 
        else:
3238
 
            source_details = entry[1][self.source_index]
3239
 
        target_details = entry[1][self.target_index]
3240
 
        target_minikind = target_details[0]
3241
 
        if path_info is not None and target_minikind in 'fdlt':
3242
 
            if not (self.target_index == 0):
3243
 
                raise AssertionError()
3244
 
            link_or_sha1 = update_entry(self.state, entry,
3245
 
                abspath=path_info[4], stat_value=path_info[3])
3246
 
            # The entry may have been modified by update_entry
3247
 
            target_details = entry[1][self.target_index]
3248
 
            target_minikind = target_details[0]
3249
 
        else:
3250
 
            link_or_sha1 = None
3251
 
        file_id = entry[0][2]
3252
 
        source_minikind = source_details[0]
3253
 
        if source_minikind in 'fdltr' and target_minikind in 'fdlt':
3254
 
            # claimed content in both: diff
3255
 
            #   r    | fdlt   |      | add source to search, add id path move and perform
3256
 
            #        |        |      | diff check on source-target
3257
 
            #   r    | fdlt   |  a   | dangling file that was present in the basis.
3258
 
            #        |        |      | ???
3259
 
            if source_minikind in 'r':
3260
 
                # add the source to the search path to find any children it
3261
 
                # has.  TODO ? : only add if it is a container ?
3262
 
                if not osutils.is_inside_any(self.searched_specific_files,
3263
 
                                             source_details[1]):
3264
 
                    self.search_specific_files.add(source_details[1])
3265
 
                # generate the old path; this is needed for stating later
3266
 
                # as well.
3267
 
                old_path = source_details[1]
3268
 
                old_dirname, old_basename = os.path.split(old_path)
3269
 
                path = pathjoin(entry[0][0], entry[0][1])
3270
 
                old_entry = self.state._get_entry(self.source_index,
3271
 
                                             path_utf8=old_path)
3272
 
                # update the source details variable to be the real
3273
 
                # location.
3274
 
                if old_entry == (None, None):
3275
 
                    raise errors.CorruptDirstate(self.state._filename,
3276
 
                        "entry '%s/%s' is considered renamed from %r"
3277
 
                        " but source does not exist\n"
3278
 
                        "entry: %s" % (entry[0][0], entry[0][1], old_path, entry))
3279
 
                source_details = old_entry[1][self.source_index]
3280
 
                source_minikind = source_details[0]
3281
 
            else:
3282
 
                old_dirname = entry[0][0]
3283
 
                old_basename = entry[0][1]
3284
 
                old_path = path = None
3285
 
            if path_info is None:
3286
 
                # the file is missing on disk, show as removed.
3287
 
                content_change = True
3288
 
                target_kind = None
3289
 
                target_exec = False
3290
 
            else:
3291
 
                # source and target are both versioned and disk file is present.
3292
 
                target_kind = path_info[2]
3293
 
                if target_kind == 'directory':
3294
 
                    if path is None:
3295
 
                        old_path = path = pathjoin(old_dirname, old_basename)
3296
 
                    self.new_dirname_to_file_id[path] = file_id
3297
 
                    if source_minikind != 'd':
3298
 
                        content_change = True
3299
 
                    else:
3300
 
                        # directories have no fingerprint
3301
 
                        content_change = False
3302
 
                    target_exec = False
3303
 
                elif target_kind == 'file':
3304
 
                    if source_minikind != 'f':
3305
 
                        content_change = True
3306
 
                    else:
3307
 
                        # Check the sha. We can't just rely on the size as
3308
 
                        # content filtering may mean differ sizes actually
3309
 
                        # map to the same content
3310
 
                        if link_or_sha1 is None:
3311
 
                            # Stat cache miss:
3312
 
                            statvalue, link_or_sha1 = \
3313
 
                                self.state._sha1_provider.stat_and_sha1(
3314
 
                                path_info[4])
3315
 
                            self.state._observed_sha1(entry, link_or_sha1,
3316
 
                                statvalue)
3317
 
                        content_change = (link_or_sha1 != source_details[1])
3318
 
                    # Target details is updated at update_entry time
3319
 
                    if self.use_filesystem_for_exec:
3320
 
                        # We don't need S_ISREG here, because we are sure
3321
 
                        # we are dealing with a file.
3322
 
                        target_exec = bool(stat.S_IEXEC & path_info[3].st_mode)
3323
 
                    else:
3324
 
                        target_exec = target_details[3]
3325
 
                elif target_kind == 'symlink':
3326
 
                    if source_minikind != 'l':
3327
 
                        content_change = True
3328
 
                    else:
3329
 
                        content_change = (link_or_sha1 != source_details[1])
3330
 
                    target_exec = False
3331
 
                elif target_kind == 'tree-reference':
3332
 
                    if source_minikind != 't':
3333
 
                        content_change = True
3334
 
                    else:
3335
 
                        content_change = False
3336
 
                    target_exec = False
3337
 
                else:
3338
 
                    if path is None:
3339
 
                        path = pathjoin(old_dirname, old_basename)
3340
 
                    raise errors.BadFileKindError(path, path_info[2])
3341
 
            if source_minikind == 'd':
3342
 
                if path is None:
3343
 
                    old_path = path = pathjoin(old_dirname, old_basename)
3344
 
                self.old_dirname_to_file_id[old_path] = file_id
3345
 
            # parent id is the entry for the path in the target tree
3346
 
            if old_basename and old_dirname == self.last_source_parent[0]:
3347
 
                source_parent_id = self.last_source_parent[1]
3348
 
            else:
3349
 
                try:
3350
 
                    source_parent_id = self.old_dirname_to_file_id[old_dirname]
3351
 
                except KeyError:
3352
 
                    source_parent_entry = self.state._get_entry(self.source_index,
3353
 
                                                           path_utf8=old_dirname)
3354
 
                    source_parent_id = source_parent_entry[0][2]
3355
 
                if source_parent_id == entry[0][2]:
3356
 
                    # This is the root, so the parent is None
3357
 
                    source_parent_id = None
3358
 
                else:
3359
 
                    self.last_source_parent[0] = old_dirname
3360
 
                    self.last_source_parent[1] = source_parent_id
3361
 
            new_dirname = entry[0][0]
3362
 
            if entry[0][1] and new_dirname == self.last_target_parent[0]:
3363
 
                target_parent_id = self.last_target_parent[1]
3364
 
            else:
3365
 
                try:
3366
 
                    target_parent_id = self.new_dirname_to_file_id[new_dirname]
3367
 
                except KeyError:
3368
 
                    # TODO: We don't always need to do the lookup, because the
3369
 
                    #       parent entry will be the same as the source entry.
3370
 
                    target_parent_entry = self.state._get_entry(self.target_index,
3371
 
                                                           path_utf8=new_dirname)
3372
 
                    if target_parent_entry == (None, None):
3373
 
                        raise AssertionError(
3374
 
                            "Could not find target parent in wt: %s\nparent of: %s"
3375
 
                            % (new_dirname, entry))
3376
 
                    target_parent_id = target_parent_entry[0][2]
3377
 
                if target_parent_id == entry[0][2]:
3378
 
                    # This is the root, so the parent is None
3379
 
                    target_parent_id = None
3380
 
                else:
3381
 
                    self.last_target_parent[0] = new_dirname
3382
 
                    self.last_target_parent[1] = target_parent_id
3383
 
 
3384
 
            source_exec = source_details[3]
3385
 
            changed = (content_change
3386
 
                or source_parent_id != target_parent_id
3387
 
                or old_basename != entry[0][1]
3388
 
                or source_exec != target_exec
3389
 
                )
3390
 
            if not changed and not self.include_unchanged:
3391
 
                return None, False
3392
 
            else:
3393
 
                if old_path is None:
3394
 
                    old_path = path = pathjoin(old_dirname, old_basename)
3395
 
                    old_path_u = self.utf8_decode(old_path)[0]
3396
 
                    path_u = old_path_u
3397
 
                else:
3398
 
                    old_path_u = self.utf8_decode(old_path)[0]
3399
 
                    if old_path == path:
3400
 
                        path_u = old_path_u
3401
 
                    else:
3402
 
                        path_u = self.utf8_decode(path)[0]
3403
 
                source_kind = DirState._minikind_to_kind[source_minikind]
3404
 
                return (entry[0][2],
3405
 
                       (old_path_u, path_u),
3406
 
                       content_change,
3407
 
                       (True, True),
3408
 
                       (source_parent_id, target_parent_id),
3409
 
                       (self.utf8_decode(old_basename)[0], self.utf8_decode(entry[0][1])[0]),
3410
 
                       (source_kind, target_kind),
3411
 
                       (source_exec, target_exec)), changed
3412
 
        elif source_minikind in 'a' and target_minikind in 'fdlt':
3413
 
            # looks like a new file
3414
 
            path = pathjoin(entry[0][0], entry[0][1])
3415
 
            # parent id is the entry for the path in the target tree
3416
 
            # TODO: these are the same for an entire directory: cache em.
3417
 
            parent_id = self.state._get_entry(self.target_index,
3418
 
                                         path_utf8=entry[0][0])[0][2]
3419
 
            if parent_id == entry[0][2]:
3420
 
                parent_id = None
3421
 
            if path_info is not None:
3422
 
                # Present on disk:
3423
 
                if self.use_filesystem_for_exec:
3424
 
                    # We need S_ISREG here, because we aren't sure if this
3425
 
                    # is a file or not.
3426
 
                    target_exec = bool(
3427
 
                        stat.S_ISREG(path_info[3].st_mode)
3428
 
                        and stat.S_IEXEC & path_info[3].st_mode)
3429
 
                else:
3430
 
                    target_exec = target_details[3]
3431
 
                return (entry[0][2],
3432
 
                       (None, self.utf8_decode(path)[0]),
3433
 
                       True,
3434
 
                       (False, True),
3435
 
                       (None, parent_id),
3436
 
                       (None, self.utf8_decode(entry[0][1])[0]),
3437
 
                       (None, path_info[2]),
3438
 
                       (None, target_exec)), True
3439
 
            else:
3440
 
                # Its a missing file, report it as such.
3441
 
                return (entry[0][2],
3442
 
                       (None, self.utf8_decode(path)[0]),
3443
 
                       False,
3444
 
                       (False, True),
3445
 
                       (None, parent_id),
3446
 
                       (None, self.utf8_decode(entry[0][1])[0]),
3447
 
                       (None, None),
3448
 
                       (None, False)), True
3449
 
        elif source_minikind in 'fdlt' and target_minikind in 'a':
3450
 
            # unversioned, possibly, or possibly not deleted: we dont care.
3451
 
            # if its still on disk, *and* theres no other entry at this
3452
 
            # path [we dont know this in this routine at the moment -
3453
 
            # perhaps we should change this - then it would be an unknown.
3454
 
            old_path = pathjoin(entry[0][0], entry[0][1])
3455
 
            # parent id is the entry for the path in the target tree
3456
 
            parent_id = self.state._get_entry(self.source_index, path_utf8=entry[0][0])[0][2]
3457
 
            if parent_id == entry[0][2]:
3458
 
                parent_id = None
3459
 
            return (entry[0][2],
3460
 
                   (self.utf8_decode(old_path)[0], None),
3461
 
                   True,
3462
 
                   (True, False),
3463
 
                   (parent_id, None),
3464
 
                   (self.utf8_decode(entry[0][1])[0], None),
3465
 
                   (DirState._minikind_to_kind[source_minikind], None),
3466
 
                   (source_details[3], None)), True
3467
 
        elif source_minikind in 'fdlt' and target_minikind in 'r':
3468
 
            # a rename; could be a true rename, or a rename inherited from
3469
 
            # a renamed parent. TODO: handle this efficiently. Its not
3470
 
            # common case to rename dirs though, so a correct but slow
3471
 
            # implementation will do.
3472
 
            if not osutils.is_inside_any(self.searched_specific_files, target_details[1]):
3473
 
                self.search_specific_files.add(target_details[1])
3474
 
        elif source_minikind in 'ra' and target_minikind in 'ra':
3475
 
            # neither of the selected trees contain this file,
3476
 
            # so skip over it. This is not currently directly tested, but
3477
 
            # is indirectly via test_too_much.TestCommands.test_conflicts.
3478
 
            pass
3479
 
        else:
3480
 
            raise AssertionError("don't know how to compare "
3481
 
                "source_minikind=%r, target_minikind=%r"
3482
 
                % (source_minikind, target_minikind))
3483
 
            ## import pdb;pdb.set_trace()
3484
 
        return None, None
3485
 
 
3486
 
    def __iter__(self):
3487
 
        return self
3488
 
 
3489
 
    def _gather_result_for_consistency(self, result):
3490
 
        """Check a result we will yield to make sure we are consistent later.
3491
 
        
3492
 
        This gathers result's parents into a set to output later.
3493
 
 
3494
 
        :param result: A result tuple.
3495
 
        """
3496
 
        if not self.partial or not result[0]:
3497
 
            return
3498
 
        self.seen_ids.add(result[0])
3499
 
        new_path = result[1][1]
3500
 
        if new_path:
3501
 
            # Not the root and not a delete: queue up the parents of the path.
3502
 
            self.search_specific_file_parents.update(
3503
 
                osutils.parent_directories(new_path.encode('utf8')))
3504
 
            # Add the root directory which parent_directories does not
3505
 
            # provide.
3506
 
            self.search_specific_file_parents.add('')
3507
 
 
3508
 
    def iter_changes(self):
3509
 
        """Iterate over the changes."""
3510
 
        utf8_decode = cache_utf8._utf8_decode
3511
 
        _cmp_by_dirs = cmp_by_dirs
3512
 
        _process_entry = self._process_entry
3513
 
        search_specific_files = self.search_specific_files
3514
 
        searched_specific_files = self.searched_specific_files
3515
 
        splitpath = osutils.splitpath
3516
 
        # sketch:
3517
 
        # compare source_index and target_index at or under each element of search_specific_files.
3518
 
        # follow the following comparison table. Note that we only want to do diff operations when
3519
 
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo
3520
 
        # for the target.
3521
 
        # cases:
3522
 
        #
3523
 
        # Source | Target | disk | action
3524
 
        #   r    | fdlt   |      | add source to search, add id path move and perform
3525
 
        #        |        |      | diff check on source-target
3526
 
        #   r    | fdlt   |  a   | dangling file that was present in the basis.
3527
 
        #        |        |      | ???
3528
 
        #   r    |  a     |      | add source to search
3529
 
        #   r    |  a     |  a   |
3530
 
        #   r    |  r     |      | this path is present in a non-examined tree, skip.
3531
 
        #   r    |  r     |  a   | this path is present in a non-examined tree, skip.
3532
 
        #   a    | fdlt   |      | add new id
3533
 
        #   a    | fdlt   |  a   | dangling locally added file, skip
3534
 
        #   a    |  a     |      | not present in either tree, skip
3535
 
        #   a    |  a     |  a   | not present in any tree, skip
3536
 
        #   a    |  r     |      | not present in either tree at this path, skip as it
3537
 
        #        |        |      | may not be selected by the users list of paths.
3538
 
        #   a    |  r     |  a   | not present in either tree at this path, skip as it
3539
 
        #        |        |      | may not be selected by the users list of paths.
3540
 
        #  fdlt  | fdlt   |      | content in both: diff them
3541
 
        #  fdlt  | fdlt   |  a   | deleted locally, but not unversioned - show as deleted ?
3542
 
        #  fdlt  |  a     |      | unversioned: output deleted id for now
3543
 
        #  fdlt  |  a     |  a   | unversioned and deleted: output deleted id
3544
 
        #  fdlt  |  r     |      | relocated in this tree, so add target to search.
3545
 
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
3546
 
        #        |        |      | this id at the other path.
3547
 
        #  fdlt  |  r     |  a   | relocated in this tree, so add target to search.
3548
 
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
3549
 
        #        |        |      | this id at the other path.
3550
 
 
3551
 
        # TODO: jam 20070516 - Avoid the _get_entry lookup overhead by
3552
 
        #       keeping a cache of directories that we have seen.
3553
 
 
3554
 
        while search_specific_files:
3555
 
            # TODO: the pending list should be lexically sorted?  the
3556
 
            # interface doesn't require it.
3557
 
            current_root = search_specific_files.pop()
3558
 
            current_root_unicode = current_root.decode('utf8')
3559
 
            searched_specific_files.add(current_root)
3560
 
            # process the entries for this containing directory: the rest will be
3561
 
            # found by their parents recursively.
3562
 
            root_entries = self.state._entries_for_path(current_root)
3563
 
            root_abspath = self.tree.abspath(current_root_unicode)
3564
 
            try:
3565
 
                root_stat = os.lstat(root_abspath)
3566
 
            except OSError, e:
3567
 
                if e.errno == errno.ENOENT:
3568
 
                    # the path does not exist: let _process_entry know that.
3569
 
                    root_dir_info = None
3570
 
                else:
3571
 
                    # some other random error: hand it up.
3572
 
                    raise
3573
 
            else:
3574
 
                root_dir_info = ('', current_root,
3575
 
                    osutils.file_kind_from_stat_mode(root_stat.st_mode), root_stat,
3576
 
                    root_abspath)
3577
 
                if root_dir_info[2] == 'directory':
3578
 
                    if self.tree._directory_is_tree_reference(
3579
 
                        current_root.decode('utf8')):
3580
 
                        root_dir_info = root_dir_info[:2] + \
3581
 
                            ('tree-reference',) + root_dir_info[3:]
3582
 
 
3583
 
            if not root_entries and not root_dir_info:
3584
 
                # this specified path is not present at all, skip it.
3585
 
                continue
3586
 
            path_handled = False
3587
 
            for entry in root_entries:
3588
 
                result, changed = _process_entry(entry, root_dir_info)
3589
 
                if changed is not None:
3590
 
                    path_handled = True
3591
 
                    if changed:
3592
 
                        self._gather_result_for_consistency(result)
3593
 
                    if changed or self.include_unchanged:
3594
 
                        yield result
3595
 
            if self.want_unversioned and not path_handled and root_dir_info:
3596
 
                new_executable = bool(
3597
 
                    stat.S_ISREG(root_dir_info[3].st_mode)
3598
 
                    and stat.S_IEXEC & root_dir_info[3].st_mode)
3599
 
                yield (None,
3600
 
                       (None, current_root_unicode),
3601
 
                       True,
3602
 
                       (False, False),
3603
 
                       (None, None),
3604
 
                       (None, splitpath(current_root_unicode)[-1]),
3605
 
                       (None, root_dir_info[2]),
3606
 
                       (None, new_executable)
3607
 
                      )
3608
 
            initial_key = (current_root, '', '')
3609
 
            block_index, _ = self.state._find_block_index_from_key(initial_key)
3610
 
            if block_index == 0:
3611
 
                # we have processed the total root already, but because the
3612
 
                # initial key matched it we should skip it here.
3613
 
                block_index +=1
3614
 
            if root_dir_info and root_dir_info[2] == 'tree-reference':
3615
 
                current_dir_info = None
3616
 
            else:
3617
 
                dir_iterator = osutils._walkdirs_utf8(root_abspath, prefix=current_root)
3618
 
                try:
3619
 
                    current_dir_info = dir_iterator.next()
3620
 
                except OSError, e:
3621
 
                    # on win32, python2.4 has e.errno == ERROR_DIRECTORY, but
3622
 
                    # python 2.5 has e.errno == EINVAL,
3623
 
                    #            and e.winerror == ERROR_DIRECTORY
3624
 
                    e_winerror = getattr(e, 'winerror', None)
3625
 
                    win_errors = (ERROR_DIRECTORY, ERROR_PATH_NOT_FOUND)
3626
 
                    # there may be directories in the inventory even though
3627
 
                    # this path is not a file on disk: so mark it as end of
3628
 
                    # iterator
3629
 
                    if e.errno in (errno.ENOENT, errno.ENOTDIR, errno.EINVAL):
3630
 
                        current_dir_info = None
3631
 
                    elif (sys.platform == 'win32'
3632
 
                          and (e.errno in win_errors
3633
 
                               or e_winerror in win_errors)):
3634
 
                        current_dir_info = None
3635
 
                    else:
3636
 
                        raise
3637
 
                else:
3638
 
                    if current_dir_info[0][0] == '':
3639
 
                        # remove .bzr from iteration
3640
 
                        bzr_index = bisect.bisect_left(current_dir_info[1], ('.bzr',))
3641
 
                        if current_dir_info[1][bzr_index][0] != '.bzr':
3642
 
                            raise AssertionError()
3643
 
                        del current_dir_info[1][bzr_index]
3644
 
            # walk until both the directory listing and the versioned metadata
3645
 
            # are exhausted.
3646
 
            if (block_index < len(self.state._dirblocks) and
3647
 
                osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
3648
 
                current_block = self.state._dirblocks[block_index]
3649
 
            else:
3650
 
                current_block = None
3651
 
            while (current_dir_info is not None or
3652
 
                   current_block is not None):
3653
 
                if (current_dir_info and current_block
3654
 
                    and current_dir_info[0][0] != current_block[0]):
3655
 
                    if _cmp_by_dirs(current_dir_info[0][0], current_block[0]) < 0:
3656
 
                        # filesystem data refers to paths not covered by the dirblock.
3657
 
                        # this has two possibilities:
3658
 
                        # A) it is versioned but empty, so there is no block for it
3659
 
                        # B) it is not versioned.
3660
 
 
3661
 
                        # if (A) then we need to recurse into it to check for
3662
 
                        # new unknown files or directories.
3663
 
                        # if (B) then we should ignore it, because we don't
3664
 
                        # recurse into unknown directories.
3665
 
                        path_index = 0
3666
 
                        while path_index < len(current_dir_info[1]):
3667
 
                                current_path_info = current_dir_info[1][path_index]
3668
 
                                if self.want_unversioned:
3669
 
                                    if current_path_info[2] == 'directory':
3670
 
                                        if self.tree._directory_is_tree_reference(
3671
 
                                            current_path_info[0].decode('utf8')):
3672
 
                                            current_path_info = current_path_info[:2] + \
3673
 
                                                ('tree-reference',) + current_path_info[3:]
3674
 
                                    new_executable = bool(
3675
 
                                        stat.S_ISREG(current_path_info[3].st_mode)
3676
 
                                        and stat.S_IEXEC & current_path_info[3].st_mode)
3677
 
                                    yield (None,
3678
 
                                        (None, utf8_decode(current_path_info[0])[0]),
3679
 
                                        True,
3680
 
                                        (False, False),
3681
 
                                        (None, None),
3682
 
                                        (None, utf8_decode(current_path_info[1])[0]),
3683
 
                                        (None, current_path_info[2]),
3684
 
                                        (None, new_executable))
3685
 
                                # dont descend into this unversioned path if it is
3686
 
                                # a dir
3687
 
                                if current_path_info[2] in ('directory',
3688
 
                                                            'tree-reference'):
3689
 
                                    del current_dir_info[1][path_index]
3690
 
                                    path_index -= 1
3691
 
                                path_index += 1
3692
 
 
3693
 
                        # This dir info has been handled, go to the next
3694
 
                        try:
3695
 
                            current_dir_info = dir_iterator.next()
3696
 
                        except StopIteration:
3697
 
                            current_dir_info = None
3698
 
                    else:
3699
 
                        # We have a dirblock entry for this location, but there
3700
 
                        # is no filesystem path for this. This is most likely
3701
 
                        # because a directory was removed from the disk.
3702
 
                        # We don't have to report the missing directory,
3703
 
                        # because that should have already been handled, but we
3704
 
                        # need to handle all of the files that are contained
3705
 
                        # within.
3706
 
                        for current_entry in current_block[1]:
3707
 
                            # entry referring to file not present on disk.
3708
 
                            # advance the entry only, after processing.
3709
 
                            result, changed = _process_entry(current_entry, None)
3710
 
                            if changed is not None:
3711
 
                                if changed:
3712
 
                                    self._gather_result_for_consistency(result)
3713
 
                                if changed or self.include_unchanged:
3714
 
                                    yield result
3715
 
                        block_index +=1
3716
 
                        if (block_index < len(self.state._dirblocks) and
3717
 
                            osutils.is_inside(current_root,
3718
 
                                              self.state._dirblocks[block_index][0])):
3719
 
                            current_block = self.state._dirblocks[block_index]
3720
 
                        else:
3721
 
                            current_block = None
3722
 
                    continue
3723
 
                entry_index = 0
3724
 
                if current_block and entry_index < len(current_block[1]):
3725
 
                    current_entry = current_block[1][entry_index]
3726
 
                else:
3727
 
                    current_entry = None
3728
 
                advance_entry = True
3729
 
                path_index = 0
3730
 
                if current_dir_info and path_index < len(current_dir_info[1]):
3731
 
                    current_path_info = current_dir_info[1][path_index]
3732
 
                    if current_path_info[2] == 'directory':
3733
 
                        if self.tree._directory_is_tree_reference(
3734
 
                            current_path_info[0].decode('utf8')):
3735
 
                            current_path_info = current_path_info[:2] + \
3736
 
                                ('tree-reference',) + current_path_info[3:]
3737
 
                else:
3738
 
                    current_path_info = None
3739
 
                advance_path = True
3740
 
                path_handled = False
3741
 
                while (current_entry is not None or
3742
 
                    current_path_info is not None):
3743
 
                    if current_entry is None:
3744
 
                        # the check for path_handled when the path is advanced
3745
 
                        # will yield this path if needed.
3746
 
                        pass
3747
 
                    elif current_path_info is None:
3748
 
                        # no path is fine: the per entry code will handle it.
3749
 
                        result, changed = _process_entry(current_entry, current_path_info)
3750
 
                        if changed is not None:
3751
 
                            if changed:
3752
 
                                self._gather_result_for_consistency(result)
3753
 
                            if changed or self.include_unchanged:
3754
 
                                yield result
3755
 
                    elif (current_entry[0][1] != current_path_info[1]
3756
 
                          or current_entry[1][self.target_index][0] in 'ar'):
3757
 
                        # The current path on disk doesn't match the dirblock
3758
 
                        # record. Either the dirblock is marked as absent, or
3759
 
                        # the file on disk is not present at all in the
3760
 
                        # dirblock. Either way, report about the dirblock
3761
 
                        # entry, and let other code handle the filesystem one.
3762
 
 
3763
 
                        # Compare the basename for these files to determine
3764
 
                        # which comes first
3765
 
                        if current_path_info[1] < current_entry[0][1]:
3766
 
                            # extra file on disk: pass for now, but only
3767
 
                            # increment the path, not the entry
3768
 
                            advance_entry = False
3769
 
                        else:
3770
 
                            # entry referring to file not present on disk.
3771
 
                            # advance the entry only, after processing.
3772
 
                            result, changed = _process_entry(current_entry, None)
3773
 
                            if changed is not None:
3774
 
                                if changed:
3775
 
                                    self._gather_result_for_consistency(result)
3776
 
                                if changed or self.include_unchanged:
3777
 
                                    yield result
3778
 
                            advance_path = False
3779
 
                    else:
3780
 
                        result, changed = _process_entry(current_entry, current_path_info)
3781
 
                        if changed is not None:
3782
 
                            path_handled = True
3783
 
                            if changed:
3784
 
                                self._gather_result_for_consistency(result)
3785
 
                            if changed or self.include_unchanged:
3786
 
                                yield result
3787
 
                    if advance_entry and current_entry is not None:
3788
 
                        entry_index += 1
3789
 
                        if entry_index < len(current_block[1]):
3790
 
                            current_entry = current_block[1][entry_index]
3791
 
                        else:
3792
 
                            current_entry = None
3793
 
                    else:
3794
 
                        advance_entry = True # reset the advance flaga
3795
 
                    if advance_path and current_path_info is not None:
3796
 
                        if not path_handled:
3797
 
                            # unversioned in all regards
3798
 
                            if self.want_unversioned:
3799
 
                                new_executable = bool(
3800
 
                                    stat.S_ISREG(current_path_info[3].st_mode)
3801
 
                                    and stat.S_IEXEC & current_path_info[3].st_mode)
3802
 
                                try:
3803
 
                                    relpath_unicode = utf8_decode(current_path_info[0])[0]
3804
 
                                except UnicodeDecodeError:
3805
 
                                    raise errors.BadFilenameEncoding(
3806
 
                                        current_path_info[0], osutils._fs_enc)
3807
 
                                yield (None,
3808
 
                                    (None, relpath_unicode),
3809
 
                                    True,
3810
 
                                    (False, False),
3811
 
                                    (None, None),
3812
 
                                    (None, utf8_decode(current_path_info[1])[0]),
3813
 
                                    (None, current_path_info[2]),
3814
 
                                    (None, new_executable))
3815
 
                            # dont descend into this unversioned path if it is
3816
 
                            # a dir
3817
 
                            if current_path_info[2] in ('directory'):
3818
 
                                del current_dir_info[1][path_index]
3819
 
                                path_index -= 1
3820
 
                        # dont descend the disk iterator into any tree
3821
 
                        # paths.
3822
 
                        if current_path_info[2] == 'tree-reference':
3823
 
                            del current_dir_info[1][path_index]
3824
 
                            path_index -= 1
3825
 
                        path_index += 1
3826
 
                        if path_index < len(current_dir_info[1]):
3827
 
                            current_path_info = current_dir_info[1][path_index]
3828
 
                            if current_path_info[2] == 'directory':
3829
 
                                if self.tree._directory_is_tree_reference(
3830
 
                                    current_path_info[0].decode('utf8')):
3831
 
                                    current_path_info = current_path_info[:2] + \
3832
 
                                        ('tree-reference',) + current_path_info[3:]
3833
 
                        else:
3834
 
                            current_path_info = None
3835
 
                        path_handled = False
3836
 
                    else:
3837
 
                        advance_path = True # reset the advance flagg.
3838
 
                if current_block is not None:
3839
 
                    block_index += 1
3840
 
                    if (block_index < len(self.state._dirblocks) and
3841
 
                        osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
3842
 
                        current_block = self.state._dirblocks[block_index]
3843
 
                    else:
3844
 
                        current_block = None
3845
 
                if current_dir_info is not None:
3846
 
                    try:
3847
 
                        current_dir_info = dir_iterator.next()
3848
 
                    except StopIteration:
3849
 
                        current_dir_info = None
3850
 
        for result in self._iter_specific_file_parents():
3851
 
            yield result
3852
 
 
3853
 
    def _iter_specific_file_parents(self):
3854
 
        """Iter over the specific file parents."""
3855
 
        while self.search_specific_file_parents:
3856
 
            # Process the parent directories for the paths we were iterating.
3857
 
            # Even in extremely large trees this should be modest, so currently
3858
 
            # no attempt is made to optimise.
3859
 
            path_utf8 = self.search_specific_file_parents.pop()
3860
 
            if osutils.is_inside_any(self.searched_specific_files, path_utf8):
3861
 
                # We've examined this path.
3862
 
                continue
3863
 
            if path_utf8 in self.searched_exact_paths:
3864
 
                # We've examined this path.
3865
 
                continue
3866
 
            path_entries = self.state._entries_for_path(path_utf8)
3867
 
            # We need either one or two entries. If the path in
3868
 
            # self.target_index has moved (so the entry in source_index is in
3869
 
            # 'ar') then we need to also look for the entry for this path in
3870
 
            # self.source_index, to output the appropriate delete-or-rename.
3871
 
            selected_entries = []
3872
 
            found_item = False
3873
 
            for candidate_entry in path_entries:
3874
 
                # Find entries present in target at this path:
3875
 
                if candidate_entry[1][self.target_index][0] not in 'ar':
3876
 
                    found_item = True
3877
 
                    selected_entries.append(candidate_entry)
3878
 
                # Find entries present in source at this path:
3879
 
                elif (self.source_index is not None and
3880
 
                    candidate_entry[1][self.source_index][0] not in 'ar'):
3881
 
                    found_item = True
3882
 
                    if candidate_entry[1][self.target_index][0] == 'a':
3883
 
                        # Deleted, emit it here.
3884
 
                        selected_entries.append(candidate_entry)
3885
 
                    else:
3886
 
                        # renamed, emit it when we process the directory it
3887
 
                        # ended up at.
3888
 
                        self.search_specific_file_parents.add(
3889
 
                            candidate_entry[1][self.target_index][1])
3890
 
            if not found_item:
3891
 
                raise AssertionError(
3892
 
                    "Missing entry for specific path parent %r, %r" % (
3893
 
                    path_utf8, path_entries))
3894
 
            path_info = self._path_info(path_utf8, path_utf8.decode('utf8'))
3895
 
            for entry in selected_entries:
3896
 
                if entry[0][2] in self.seen_ids:
3897
 
                    continue
3898
 
                result, changed = self._process_entry(entry, path_info)
3899
 
                if changed is None:
3900
 
                    raise AssertionError(
3901
 
                        "Got entry<->path mismatch for specific path "
3902
 
                        "%r entry %r path_info %r " % (
3903
 
                        path_utf8, entry, path_info))
3904
 
                # Only include changes - we're outside the users requested
3905
 
                # expansion.
3906
 
                if changed:
3907
 
                    self._gather_result_for_consistency(result)
3908
 
                    if (result[6][0] == 'directory' and
3909
 
                        result[6][1] != 'directory'):
3910
 
                        # This stopped being a directory, the old children have
3911
 
                        # to be included.
3912
 
                        if entry[1][self.source_index][0] == 'r':
3913
 
                            # renamed, take the source path
3914
 
                            entry_path_utf8 = entry[1][self.source_index][1]
3915
 
                        else:
3916
 
                            entry_path_utf8 = path_utf8
3917
 
                        initial_key = (entry_path_utf8, '', '')
3918
 
                        block_index, _ = self.state._find_block_index_from_key(
3919
 
                            initial_key)
3920
 
                        if block_index == 0:
3921
 
                            # The children of the root are in block index 1.
3922
 
                            block_index +=1
3923
 
                        current_block = None
3924
 
                        if block_index < len(self.state._dirblocks):
3925
 
                            current_block = self.state._dirblocks[block_index]
3926
 
                            if not osutils.is_inside(
3927
 
                                entry_path_utf8, current_block[0]):
3928
 
                                # No entries for this directory at all.
3929
 
                                current_block = None
3930
 
                        if current_block is not None:
3931
 
                            for entry in current_block[1]:
3932
 
                                if entry[1][self.source_index][0] in 'ar':
3933
 
                                    # Not in the source tree, so doesn't have to be
3934
 
                                    # included.
3935
 
                                    continue
3936
 
                                # Path of the entry itself.
3937
 
 
3938
 
                                self.search_specific_file_parents.add(
3939
 
                                    osutils.pathjoin(*entry[0][:2]))
3940
 
                if changed or self.include_unchanged:
3941
 
                    yield result
3942
 
            self.searched_exact_paths.add(path_utf8)
3943
 
 
3944
 
    def _path_info(self, utf8_path, unicode_path):
3945
 
        """Generate path_info for unicode_path.
3946
 
 
3947
 
        :return: None if unicode_path does not exist, or a path_info tuple.
3948
 
        """
3949
 
        abspath = self.tree.abspath(unicode_path)
3950
 
        try:
3951
 
            stat = os.lstat(abspath)
3952
 
        except OSError, e:
3953
 
            if e.errno == errno.ENOENT:
3954
 
                # the path does not exist.
3955
 
                return None
3956
 
            else:
3957
 
                raise
3958
 
        utf8_basename = utf8_path.rsplit('/', 1)[-1]
3959
 
        dir_info = (utf8_path, utf8_basename,
3960
 
            osutils.file_kind_from_stat_mode(stat.st_mode), stat,
3961
 
            abspath)
3962
 
        if dir_info[2] == 'directory':
3963
 
            if self.tree._directory_is_tree_reference(
3964
 
                unicode_path):
3965
 
                self.root_dir_info = self.root_dir_info[:2] + \
3966
 
                    ('tree-reference',) + self.root_dir_info[3:]
3967
 
        return dir_info
3968
 
 
3969
 
 
3970
 
# Try to load the compiled form if possible
3971
 
try:
3972
 
    from bzrlib._dirstate_helpers_pyx import (
3973
 
        _read_dirblocks,
3974
 
        bisect_dirblock,
3975
 
        _bisect_path_left,
3976
 
        _bisect_path_right,
3977
 
        cmp_by_dirs,
3978
 
        ProcessEntryC as _process_entry,
3979
 
        update_entry as update_entry,
3980
 
        )
3981
 
except ImportError, e:
3982
 
    osutils.failed_to_load_extension(e)
3983
 
    from bzrlib._dirstate_helpers_py import (
3984
 
        _read_dirblocks,
3985
 
        bisect_dirblock,
3986
 
        _bisect_path_left,
3987
 
        _bisect_path_right,
3988
 
        cmp_by_dirs,
3989
 
        )
3990
 
    # FIXME: It would be nice to be able to track moved lines so that the
3991
 
    # corresponding python code can be moved to the _dirstate_helpers_py
3992
 
    # module. I don't want to break the history for this important piece of
3993
 
    # code so I left the code here -- vila 20090622
3994
 
    update_entry = py_update_entry
3995
 
    _process_entry = ProcessEntryPython