~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Jelmer Vernooij
  • Date: 2011-04-09 21:00:33 UTC
  • mto: (5777.5.1 inventoryworkingtree)
  • mto: This revision was merged to the branch mainline in revision 5782.
  • Revision ID: jelmer@samba.org-20110409210033-wg01c6m0qd2c3o4l
Split inventory-specific code out of MutableTree into MutableInventoryTree.

Show diffs side-by-side

added added

removed removed

Lines of Context:
20
20
lines by NL. The field delimiters are ommitted in the grammar, line delimiters
21
21
are not - this is done for clarity of reading. All string data is in utf8.
22
22
 
23
 
::
24
 
 
25
 
    MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
26
 
    NL = "\\n";
27
 
    NULL = "\\0";
28
 
    WHOLE_NUMBER = {digit}, digit;
29
 
    BOOLEAN = "y" | "n";
30
 
    REVISION_ID = a non-empty utf8 string;
31
 
    
32
 
    dirstate format = header line, full checksum, row count, parent details,
33
 
     ghost_details, entries;
34
 
    header line = "#bazaar dirstate flat format 3", NL;
35
 
    full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
36
 
    row count = "num_entries: ", WHOLE_NUMBER, NL;
37
 
    parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
38
 
    ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
39
 
    entries = {entry};
40
 
    entry = entry_key, current_entry_details, {parent_entry_details};
41
 
    entry_key = dirname,  basename, fileid;
42
 
    current_entry_details = common_entry_details, working_entry_details;
43
 
    parent_entry_details = common_entry_details, history_entry_details;
44
 
    common_entry_details = MINIKIND, fingerprint, size, executable
45
 
    working_entry_details = packed_stat
46
 
    history_entry_details = REVISION_ID;
47
 
    executable = BOOLEAN;
48
 
    size = WHOLE_NUMBER;
49
 
    fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
50
 
 
51
 
Given this definition, the following is useful to know::
52
 
 
53
 
    entry (aka row) - all the data for a given key.
54
 
    entry[0]: The key (dirname, basename, fileid)
55
 
    entry[0][0]: dirname
56
 
    entry[0][1]: basename
57
 
    entry[0][2]: fileid
58
 
    entry[1]: The tree(s) data for this path and id combination.
59
 
    entry[1][0]: The current tree
60
 
    entry[1][1]: The second tree
61
 
 
62
 
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate::
63
 
 
64
 
    entry[1][0][0]: minikind
65
 
    entry[1][0][1]: fingerprint
66
 
    entry[1][0][2]: size
67
 
    entry[1][0][3]: executable
68
 
    entry[1][0][4]: packed_stat
69
 
 
70
 
OR (for non tree-0)::
71
 
 
72
 
    entry[1][1][4]: revision_id
 
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
73
67
 
74
68
There may be multiple rows at the root, one per id present in the root, so the
75
 
in memory root row is now::
76
 
 
77
 
    self._dirblocks[0] -> ('', [entry ...]),
78
 
 
79
 
and the entries in there are::
80
 
 
81
 
    entries[0][0]: ''
82
 
    entries[0][1]: ''
83
 
    entries[0][2]: file_id
84
 
    entries[1][0]: The tree data for the current tree for this fileid at /
85
 
    etc.
86
 
 
87
 
Kinds::
88
 
 
89
 
    'r' is a relocated entry: This path is not present in this tree with this
90
 
        id, but the id can be found at another location. The fingerprint is
91
 
        used to point to the target location.
92
 
    'a' is an absent entry: In that tree the id is not present at this path.
93
 
    'd' is a directory entry: This path in this tree is a directory with the
94
 
        current file id. There is no fingerprint for directories.
95
 
    'f' is a file entry: As for directory, but it's a file. The fingerprint is
96
 
        the sha1 value of the file's canonical form, i.e. after any read
97
 
        filters have been applied to the convenience form stored in the working
98
 
        tree.
99
 
    'l' is a symlink entry: As for directory, but a symlink. The fingerprint is
100
 
        the link target.
101
 
    't' is a reference to a nested subtree; the fingerprint is the referenced
102
 
        revision.
 
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.
103
92
 
104
93
Ordering:
105
94
 
106
 
The entries on disk and in memory are ordered according to the following keys::
 
95
The entries on disk and in memory are ordered according to the following keys:
107
96
 
108
97
    directory, as a list of components
109
98
    filename
110
99
    file-id
111
100
 
112
101
--- Format 1 had the following different definition: ---
113
 
 
114
 
::
115
 
 
116
 
    rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
117
 
        WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
118
 
        {PARENT ROW}
119
 
    PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
120
 
        basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
121
 
        SHA1
 
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
122
108
 
123
109
PARENT ROW's are emitted for every parent that is not in the ghosts details
124
110
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
149
135
----
150
136
 
151
137
Design priorities:
152
 
 1. Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
153
 
 2. fall back current object model as needed.
154
 
 3. scale usably to the largest trees known today - say 50K entries. (mozilla
 
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
155
141
    is an example of this)
156
142
 
157
143
 
158
144
Locking:
159
 
 
160
145
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
161
146
 been modified, but will require that we flush/ignore cached stat-hit data
162
147
 because we won't want to restat all files on disk just because a lock was
163
148
 acquired, yet we cannot trust the data after the previous lock was released.
164
149
 
165
 
Memory representation::
166
 
 
 
150
Memory representation:
167
151
 vector of all directories, and vector of the childen ?
168
152
   i.e.
169
153
     root_entrie = (direntry for root, [parent_direntries_for_root]),
183
167
    - What's the risk of error here? Once we have the base format being processed
184
168
      we should have a net win regardless of optimality. So we are going to
185
169
      go with what seems reasonable.
186
 
 
187
170
open questions:
188
171
 
189
172
Maybe we should do a test profile of the core structure - 10K simulated
219
202
"""
220
203
 
221
204
import bisect
 
205
import binascii
222
206
import errno
223
207
import operator
224
208
import os
225
209
from stat import S_IEXEC
226
210
import stat
 
211
import struct
227
212
import sys
228
213
import time
229
214
import zlib
230
215
 
231
216
from bzrlib import (
232
217
    cache_utf8,
233
 
    config,
234
218
    debug,
235
219
    errors,
236
220
    inventory,
238
222
    osutils,
239
223
    static_tuple,
240
224
    trace,
241
 
    urlutils,
242
225
    )
243
226
 
244
227
 
249
232
ERROR_DIRECTORY = 267
250
233
 
251
234
 
 
235
if not getattr(struct, '_compile', None):
 
236
    # Cannot pre-compile the dirstate pack_stat
 
237
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
 
238
        """Convert stat values into a packed representation."""
 
239
        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),
 
240
            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,
 
241
            st.st_mode))[:-1]
 
242
else:
 
243
    # compile the struct compiler we need, so as to only do it once
 
244
    from _struct import Struct
 
245
    _compiled_pack = Struct('>LLLLLL').pack
 
246
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):
 
247
        """Convert stat values into a packed representation."""
 
248
        # jam 20060614 it isn't really worth removing more entries if we
 
249
        # are going to leave it in packed form.
 
250
        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
 
251
        # With all entries, filesize is 5.9M and read time is maybe 280ms
 
252
        # well within the noise margin
 
253
 
 
254
        # base64 encoding always adds a final newline, so strip it off
 
255
        # The current version
 
256
        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),
 
257
            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
258
        # This is 0.060s / 1.520s faster by not encoding as much information
 
259
        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
 
260
        # This is not strictly faster than _encode(_pack())[:-1]
 
261
        # return '%X.%X.%X.%X.%X.%X' % (
 
262
        #      st.st_size, int(st.st_mtime), int(st.st_ctime),
 
263
        #      st.st_dev, st.st_ino, st.st_mode)
 
264
        # Similar to the _encode(_pack('>LL'))
 
265
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
 
266
 
 
267
 
 
268
def _unpack_stat(packed_stat):
 
269
    """Turn a packed_stat back into the stat fields.
 
270
 
 
271
    This is meant as a debugging tool, should not be used in real code.
 
272
    """
 
273
    (st_size, st_mtime, st_ctime, st_dev, st_ino,
 
274
     st_mode) = struct.unpack('>LLLLLL', binascii.a2b_base64(packed_stat))
 
275
    return dict(st_size=st_size, st_mtime=st_mtime, st_ctime=st_ctime,
 
276
                st_dev=st_dev, st_ino=st_ino, st_mode=st_mode)
 
277
 
 
278
 
252
279
class SHA1Provider(object):
253
280
    """An interface for getting sha1s of a file."""
254
281
 
339
366
    NOT_IN_MEMORY = 0
340
367
    IN_MEMORY_UNMODIFIED = 1
341
368
    IN_MEMORY_MODIFIED = 2
342
 
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
343
369
 
344
370
    # A pack_stat (the x's) that is just noise and will never match the output
345
371
    # of base64 encode.
346
372
    NULLSTAT = 'x' * 32
347
 
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
 
373
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
348
374
 
349
375
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
350
376
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
351
377
 
352
 
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
 
378
    def __init__(self, path, sha1_provider):
353
379
        """Create a  DirState object.
354
380
 
355
381
        :param path: The path at which the dirstate file on disk should live.
356
382
        :param sha1_provider: an object meeting the SHA1Provider interface.
357
 
        :param worth_saving_limit: when the exact number of hash changed
358
 
            entries is known, only bother saving the dirstate if more than
359
 
            this count of entries have changed.
360
 
            -1 means never save hash changes, 0 means always save hash changes.
361
383
        """
362
384
        # _header_state and _dirblock_state represent the current state
363
385
        # of the dirstate metadata and the per-row data respectiely.
400
422
        # during commit.
401
423
        self._last_block_index = None
402
424
        self._last_entry_index = None
403
 
        # The set of known hash changes
404
 
        self._known_hash_changes = set()
405
 
        # How many hash changed entries can we have without saving
406
 
        self._worth_saving_limit = worth_saving_limit
407
 
        self._config_stack = config.LocationStack(urlutils.local_path_to_url(
408
 
            path))
409
425
 
410
426
    def __repr__(self):
411
427
        return "%s(%r)" % \
412
428
            (self.__class__.__name__, self._filename)
413
429
 
414
 
    def _mark_modified(self, hash_changed_entries=None, header_modified=False):
415
 
        """Mark this dirstate as modified.
416
 
 
417
 
        :param hash_changed_entries: if non-None, mark just these entries as
418
 
            having their hash modified.
419
 
        :param header_modified: mark the header modified as well, not just the
420
 
            dirblocks.
421
 
        """
422
 
        #trace.mutter_callsite(3, "modified hash entries: %s", hash_changed_entries)
423
 
        if hash_changed_entries:
424
 
            self._known_hash_changes.update([e[0] for e in hash_changed_entries])
425
 
            if self._dirblock_state in (DirState.NOT_IN_MEMORY,
426
 
                                        DirState.IN_MEMORY_UNMODIFIED):
427
 
                # If the dirstate is already marked a IN_MEMORY_MODIFIED, then
428
 
                # that takes precedence.
429
 
                self._dirblock_state = DirState.IN_MEMORY_HASH_MODIFIED
430
 
        else:
431
 
            # TODO: Since we now have a IN_MEMORY_HASH_MODIFIED state, we
432
 
            #       should fail noisily if someone tries to set
433
 
            #       IN_MEMORY_MODIFIED but we don't have a write-lock!
434
 
            # We don't know exactly what changed so disable smart saving
435
 
            self._dirblock_state = DirState.IN_MEMORY_MODIFIED
436
 
        if header_modified:
437
 
            self._header_state = DirState.IN_MEMORY_MODIFIED
438
 
 
439
 
    def _mark_unmodified(self):
440
 
        """Mark this dirstate as unmodified."""
441
 
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
442
 
        self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
443
 
        self._known_hash_changes = set()
444
 
 
445
430
    def add(self, path, file_id, kind, stat, fingerprint):
446
431
        """Add a path to be tracked.
447
432
 
573
558
        if kind == 'directory':
574
559
           # insert a new dirblock
575
560
           self._ensure_block(block_index, entry_index, utf8path)
576
 
        self._mark_modified()
 
561
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
577
562
        if self._id_index:
578
563
            self._add_to_id_index(self._id_index, entry_key)
579
564
 
1045
1030
 
1046
1031
        self._ghosts = []
1047
1032
        self._parents = [parents[0]]
1048
 
        self._mark_modified(header_modified=True)
 
1033
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1034
        self._header_state = DirState.IN_MEMORY_MODIFIED
1049
1035
 
1050
1036
    def _empty_parent_info(self):
1051
1037
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1180
1166
    def _fields_per_entry(self):
1181
1167
        """How many null separated fields should be in each entry row.
1182
1168
 
1183
 
        Each line now has an extra '\\n' field which is not used
 
1169
        Each line now has an extra '\n' field which is not used
1184
1170
        so we just skip over it
1185
 
 
1186
 
        entry size::
 
1171
        entry size:
1187
1172
            3 fields for the key
1188
1173
            + number of fields per tree_data (5) * tree count
1189
1174
            + newline
1302
1287
            raise
1303
1288
        return result
1304
1289
 
1305
 
    def _check_delta_is_valid(self, delta):
1306
 
        return list(inventory._check_delta_unique_ids(
1307
 
                    inventory._check_delta_unique_old_paths(
1308
 
                    inventory._check_delta_unique_new_paths(
1309
 
                    inventory._check_delta_ids_match_entry(
1310
 
                    inventory._check_delta_ids_are_valid(
1311
 
                    inventory._check_delta_new_path_entry_both_or_None(delta)))))))
1312
 
 
1313
1290
    def update_by_delta(self, delta):
1314
1291
        """Apply an inventory delta to the dirstate for tree 0
1315
1292
 
1333
1310
        new_ids = set()
1334
1311
        # This loop transforms the delta to single atomic operations that can
1335
1312
        # be executed and validated.
1336
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1337
 
        for old_path, new_path, file_id, inv_entry in delta:
 
1313
        for old_path, new_path, file_id, inv_entry in sorted(
 
1314
            inventory._check_delta_unique_old_paths(
 
1315
            inventory._check_delta_unique_new_paths(
 
1316
            inventory._check_delta_ids_match_entry(
 
1317
            inventory._check_delta_ids_are_valid(
 
1318
            inventory._check_delta_new_path_entry_both_or_None(delta))))),
 
1319
            reverse=True):
1338
1320
            if (file_id in insertions) or (file_id in removals):
1339
 
                self._raise_invalid(old_path or new_path, file_id,
 
1321
                raise errors.InconsistentDelta(old_path or new_path, file_id,
1340
1322
                    "repeated file_id")
1341
1323
            if old_path is not None:
1342
1324
                old_path = old_path.encode('utf-8')
1345
1327
                new_ids.add(file_id)
1346
1328
            if new_path is not None:
1347
1329
                if inv_entry is None:
1348
 
                    self._raise_invalid(new_path, file_id,
 
1330
                    raise errors.InconsistentDelta(new_path, file_id,
1349
1331
                        "new_path with no entry")
1350
1332
                new_path = new_path.encode('utf-8')
1351
1333
                dirname_utf8, basename = osutils.split(new_path)
1392
1374
            # _get_entry raises BzrError when a request is inconsistent; we
1393
1375
            # want such errors to be shown as InconsistentDelta - and that 
1394
1376
            # fits the behaviour we trigger.
1395
 
            raise errors.InconsistentDeltaDelta(delta,
1396
 
                "error from _get_entry. %s" % (e,))
 
1377
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1397
1378
 
1398
1379
    def _apply_removals(self, removals):
1399
1380
        for file_id, path in sorted(removals, reverse=True,
1404
1385
            try:
1405
1386
                entry = self._dirblocks[block_i][1][entry_i]
1406
1387
            except IndexError:
1407
 
                self._raise_invalid(path, file_id,
 
1388
                self._changes_aborted = True
 
1389
                raise errors.InconsistentDelta(path, file_id,
1408
1390
                    "Wrong path for old path.")
1409
1391
            if not f_present or entry[1][0][0] in 'ar':
1410
 
                self._raise_invalid(path, file_id,
 
1392
                self._changes_aborted = True
 
1393
                raise errors.InconsistentDelta(path, file_id,
1411
1394
                    "Wrong path for old path.")
1412
1395
            if file_id != entry[0][2]:
1413
 
                self._raise_invalid(path, file_id,
 
1396
                self._changes_aborted = True
 
1397
                raise errors.InconsistentDelta(path, file_id,
1414
1398
                    "Attempt to remove path has wrong id - found %r."
1415
1399
                    % entry[0][2])
1416
1400
            self._make_absent(entry)
1426
1410
                # be due to it being in a parent tree, or a corrupt delta.
1427
1411
                for child_entry in self._dirblocks[block_i][1]:
1428
1412
                    if child_entry[1][0][0] not in ('r', 'a'):
1429
 
                        self._raise_invalid(path, entry[0][2],
 
1413
                        self._changes_aborted = True
 
1414
                        raise errors.InconsistentDelta(path, entry[0][2],
1430
1415
                            "The file id was deleted but its children were "
1431
1416
                            "not deleted.")
1432
1417
 
1436
1421
                self.update_minimal(key, minikind, executable, fingerprint,
1437
1422
                                    path_utf8=path_utf8)
1438
1423
        except errors.NotVersionedError:
1439
 
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
 
1424
            self._changes_aborted = True
 
1425
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
1440
1426
                "Missing parent")
1441
1427
 
1442
1428
    def update_basis_by_delta(self, delta, new_revid):
1450
1436
        Note that an exception during the operation of this method will leave
1451
1437
        the dirstate in a corrupt state where it should not be saved.
1452
1438
 
 
1439
        Finally, we expect all changes to be synchronising the basis tree with
 
1440
        the working tree.
 
1441
 
1453
1442
        :param new_revid: The new revision id for the trees parent.
1454
1443
        :param delta: An inventory delta (see apply_inventory_delta) describing
1455
1444
            the changes from the current left most parent revision to new_revid.
1467
1456
 
1468
1457
        self._parents[0] = new_revid
1469
1458
 
1470
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1459
        delta = sorted(delta, reverse=True)
1471
1460
        adds = []
1472
1461
        changes = []
1473
1462
        deletes = []
1494
1483
        new_ids = set()
1495
1484
        for old_path, new_path, file_id, inv_entry in delta:
1496
1485
            if inv_entry is not None and file_id != inv_entry.file_id:
1497
 
                self._raise_invalid(new_path, file_id,
 
1486
                raise errors.InconsistentDelta(new_path, file_id,
1498
1487
                    "mismatched entry file_id %r" % inv_entry)
1499
 
            if new_path is None:
1500
 
                new_path_utf8 = None
1501
 
            else:
 
1488
            if new_path is not None:
1502
1489
                if inv_entry is None:
1503
 
                    self._raise_invalid(new_path, file_id,
 
1490
                    raise errors.InconsistentDelta(new_path, file_id,
1504
1491
                        "new_path with no entry")
1505
1492
                new_path_utf8 = encode(new_path)
1506
1493
                # note the parent for validation
1508
1495
                if basename_utf8:
1509
1496
                    parents.add((dirname_utf8, inv_entry.parent_id))
1510
1497
            if old_path is None:
1511
 
                old_path_utf8 = None
1512
 
            else:
1513
 
                old_path_utf8 = encode(old_path)
1514
 
            if old_path is None:
1515
 
                adds.append((None, new_path_utf8, file_id,
 
1498
                adds.append((None, encode(new_path), file_id,
1516
1499
                    inv_to_entry(inv_entry), True))
1517
1500
                new_ids.add(file_id)
1518
1501
            elif new_path is None:
1519
 
                deletes.append((old_path_utf8, None, file_id, None, True))
1520
 
            elif (old_path, new_path) == root_only:
1521
 
                # change things in-place
1522
 
                # Note: the case of a parent directory changing its file_id
1523
 
                #       tends to break optimizations here, because officially
1524
 
                #       the file has actually been moved, it just happens to
1525
 
                #       end up at the same path. If we can figure out how to
1526
 
                #       handle that case, we can avoid a lot of add+delete
1527
 
                #       pairs for objects that stay put.
1528
 
                # elif old_path == new_path:
1529
 
                changes.append((old_path_utf8, new_path_utf8, file_id,
1530
 
                                inv_to_entry(inv_entry)))
1531
 
            else:
 
1502
                deletes.append((encode(old_path), None, file_id, None, True))
 
1503
            elif (old_path, new_path) != root_only:
1532
1504
                # Renames:
1533
1505
                # Because renames must preserve their children we must have
1534
1506
                # processed all relocations and removes before hand. The sort
1544
1516
                self._update_basis_apply_deletes(deletes)
1545
1517
                deletes = []
1546
1518
                # Split into an add/delete pair recursively.
1547
 
                adds.append((old_path_utf8, new_path_utf8, file_id,
1548
 
                             inv_to_entry(inv_entry), False))
 
1519
                adds.append((None, new_path_utf8, file_id,
 
1520
                    inv_to_entry(inv_entry), False))
1549
1521
                # Expunge deletes that we've seen so that deleted/renamed
1550
1522
                # children of a rename directory are handled correctly.
1551
 
                new_deletes = reversed(list(
1552
 
                    self._iter_child_entries(1, old_path_utf8)))
 
1523
                new_deletes = reversed(list(self._iter_child_entries(1,
 
1524
                    encode(old_path))))
1553
1525
                # Remove the current contents of the tree at orig_path, and
1554
1526
                # reinsert at the correct new path.
1555
1527
                for entry in new_deletes:
1556
 
                    child_dirname, child_basename, child_file_id = entry[0]
1557
 
                    if child_dirname:
1558
 
                        source_path = child_dirname + '/' + child_basename
 
1528
                    if entry[0][0]:
 
1529
                        source_path = entry[0][0] + '/' + entry[0][1]
1559
1530
                    else:
1560
 
                        source_path = child_basename
 
1531
                        source_path = entry[0][1]
1561
1532
                    if new_path_utf8:
1562
1533
                        target_path = new_path_utf8 + source_path[len(old_path):]
1563
1534
                    else:
1564
1535
                        if old_path == '':
1565
1536
                            raise AssertionError("cannot rename directory to"
1566
 
                                                 " itself")
 
1537
                                " itself")
1567
1538
                        target_path = source_path[len(old_path) + 1:]
1568
1539
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1569
1540
                    deletes.append(
1570
1541
                        (source_path, target_path, entry[0][2], None, False))
1571
 
                deletes.append((old_path_utf8, new_path, file_id, None, False))
 
1542
                deletes.append(
 
1543
                    (encode(old_path), new_path, file_id, None, False))
 
1544
            else:
 
1545
                # changes to just the root should not require remove/insertion
 
1546
                # of everything.
 
1547
                changes.append((encode(old_path), encode(new_path), file_id,
 
1548
                    inv_to_entry(inv_entry)))
1572
1549
        self._check_delta_ids_absent(new_ids, delta, 1)
1573
1550
        try:
1574
1551
            # Finish expunging deletes/first half of renames.
1584
1561
            if 'integrity error' not in str(e):
1585
1562
                raise
1586
1563
            # _get_entry raises BzrError when a request is inconsistent; we
1587
 
            # want such errors to be shown as InconsistentDelta - and that
1588
 
            # fits the behaviour we trigger.
1589
 
            raise errors.InconsistentDeltaDelta(delta,
1590
 
                "error from _get_entry. %s" % (e,))
 
1564
            # want such errors to be shown as InconsistentDelta - and that 
 
1565
            # fits the behaviour we trigger. Partof this is driven by dirstate
 
1566
            # only supporting deltas that turn the basis into a closer fit to
 
1567
            # the active tree.
 
1568
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1591
1569
 
1592
 
        self._mark_modified(header_modified=True)
 
1570
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1571
        self._header_state = DirState.IN_MEMORY_MODIFIED
1593
1572
        self._id_index = None
1594
1573
        return
1595
1574
 
1609
1588
                if entry[0][2] != file_id:
1610
1589
                    # Different file_id, so not what we want.
1611
1590
                    continue
1612
 
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
 
1591
                # NB: No changes made before this helper is called, so no need
 
1592
                # to set the _changes_aborted flag.
 
1593
                raise errors.InconsistentDelta(
 
1594
                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
1613
1595
                    "This file_id is new in the delta but already present in "
1614
1596
                    "the target")
1615
1597
 
1616
 
    def _raise_invalid(self, path, file_id, reason):
1617
 
        self._changes_aborted = True
1618
 
        raise errors.InconsistentDelta(path, file_id, reason)
1619
 
 
1620
1598
    def _update_basis_apply_adds(self, adds):
1621
1599
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1622
1600
 
1630
1608
        """
1631
1609
        # Adds are accumulated partly from renames, so can be in any input
1632
1610
        # order - sort it.
1633
 
        # TODO: we may want to sort in dirblocks order. That way each entry
1634
 
        #       will end up in the same directory, allowing the _get_entry
1635
 
        #       fast-path for looking up 2 items in the same dir work.
1636
 
        adds.sort(key=lambda x: x[1])
 
1611
        adds.sort()
1637
1612
        # adds is now in lexographic order, which places all parents before
1638
1613
        # their children, so we can process it linearly.
1639
1614
        absent = 'ar'
1640
 
        st = static_tuple.StaticTuple
1641
1615
        for old_path, new_path, file_id, new_details, real_add in adds:
1642
 
            dirname, basename = osutils.split(new_path)
1643
 
            entry_key = st(dirname, basename, file_id)
1644
 
            block_index, present = self._find_block_index_from_key(entry_key)
1645
 
            if not present:
1646
 
                self._raise_invalid(new_path, file_id,
1647
 
                    "Unable to find block for this record."
1648
 
                    " Was the parent added?")
1649
 
            block = self._dirblocks[block_index][1]
1650
 
            entry_index, present = self._find_entry_index(entry_key, block)
1651
 
            if real_add:
1652
 
                if old_path is not None:
1653
 
                    self._raise_invalid(new_path, file_id,
1654
 
                        'considered a real add but still had old_path at %s'
1655
 
                        % (old_path,))
1656
 
            if present:
1657
 
                entry = block[entry_index]
1658
 
                basis_kind = entry[1][1][0]
1659
 
                if basis_kind == 'a':
1660
 
                    entry[1][1] = new_details
1661
 
                elif basis_kind == 'r':
1662
 
                    raise NotImplementedError()
1663
 
                else:
1664
 
                    self._raise_invalid(new_path, file_id,
1665
 
                        "An entry was marked as a new add"
1666
 
                        " but the basis target already existed")
1667
 
            else:
1668
 
                # The exact key was not found in the block. However, we need to
1669
 
                # check if there is a key next to us that would have matched.
1670
 
                # We only need to check 2 locations, because there are only 2
1671
 
                # trees present.
1672
 
                for maybe_index in range(entry_index-1, entry_index+1):
1673
 
                    if maybe_index < 0 or maybe_index >= len(block):
1674
 
                        continue
1675
 
                    maybe_entry = block[maybe_index]
1676
 
                    if maybe_entry[0][:2] != (dirname, basename):
1677
 
                        # Just a random neighbor
1678
 
                        continue
1679
 
                    if maybe_entry[0][2] == file_id:
1680
 
                        raise AssertionError(
1681
 
                            '_find_entry_index didnt find a key match'
1682
 
                            ' but walking the data did, for %s'
1683
 
                            % (entry_key,))
1684
 
                    basis_kind = maybe_entry[1][1][0]
1685
 
                    if basis_kind not in 'ar':
1686
 
                        self._raise_invalid(new_path, file_id,
1687
 
                            "we have an add record for path, but the path"
1688
 
                            " is already present with another file_id %s"
1689
 
                            % (maybe_entry[0][2],))
1690
 
 
1691
 
                entry = (entry_key, [DirState.NULL_PARENT_DETAILS,
1692
 
                                     new_details])
1693
 
                block.insert(entry_index, entry)
1694
 
 
1695
 
            active_kind = entry[1][0][0]
1696
 
            if active_kind == 'a':
1697
 
                # The active record shows up as absent, this could be genuine,
1698
 
                # or it could be present at some other location. We need to
1699
 
                # verify.
1700
 
                id_index = self._get_id_index()
1701
 
                # The id_index may not be perfectly accurate for tree1, because
1702
 
                # we haven't been keeping it updated. However, it should be
1703
 
                # fine for tree0, and that gives us enough info for what we
1704
 
                # need
1705
 
                keys = id_index.get(file_id, ())
1706
 
                for key in keys:
1707
 
                    block_i, entry_i, d_present, f_present = \
1708
 
                        self._get_block_entry_index(key[0], key[1], 0)
1709
 
                    if not f_present:
1710
 
                        continue
1711
 
                    active_entry = self._dirblocks[block_i][1][entry_i]
1712
 
                    if (active_entry[0][2] != file_id):
1713
 
                        # Some other file is at this path, we don't need to
1714
 
                        # link it.
1715
 
                        continue
1716
 
                    real_active_kind = active_entry[1][0][0]
1717
 
                    if real_active_kind in 'ar':
1718
 
                        # We found a record, which was not *this* record,
1719
 
                        # which matches the file_id, but is not actually
1720
 
                        # present. Something seems *really* wrong.
1721
 
                        self._raise_invalid(new_path, file_id,
1722
 
                            "We found a tree0 entry that doesnt make sense")
1723
 
                    # Now, we've found a tree0 entry which matches the file_id
1724
 
                    # but is at a different location. So update them to be
1725
 
                    # rename records.
1726
 
                    active_dir, active_name = active_entry[0][:2]
1727
 
                    if active_dir:
1728
 
                        active_path = active_dir + '/' + active_name
1729
 
                    else:
1730
 
                        active_path = active_name
1731
 
                    active_entry[1][1] = st('r', new_path, 0, False, '')
1732
 
                    entry[1][0] = st('r', active_path, 0, False, '')
1733
 
            elif active_kind == 'r':
1734
 
                raise NotImplementedError()
1735
 
 
1736
 
            new_kind = new_details[0]
1737
 
            if new_kind == 'd':
1738
 
                self._ensure_block(block_index, entry_index, new_path)
 
1616
            # the entry for this file_id must be in tree 0.
 
1617
            entry = self._get_entry(0, file_id, new_path)
 
1618
            if entry[0] is None or entry[0][2] != file_id:
 
1619
                self._changes_aborted = True
 
1620
                raise errors.InconsistentDelta(new_path, file_id,
 
1621
                    'working tree does not contain new entry')
 
1622
            if real_add and entry[1][1][0] not in absent:
 
1623
                self._changes_aborted = True
 
1624
                raise errors.InconsistentDelta(new_path, file_id,
 
1625
                    'The entry was considered to be a genuinely new record,'
 
1626
                    ' but there was already an old record for it.')
 
1627
            # We don't need to update the target of an 'r' because the handling
 
1628
            # of renames turns all 'r' situations into a delete at the original
 
1629
            # location.
 
1630
            entry[1][1] = new_details
1739
1631
 
1740
1632
    def _update_basis_apply_changes(self, changes):
1741
1633
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1746
1638
        absent = 'ar'
1747
1639
        for old_path, new_path, file_id, new_details in changes:
1748
1640
            # the entry for this file_id must be in tree 0.
1749
 
            entry = self._get_entry(1, file_id, new_path)
1750
 
            if entry[0] is None or entry[1][1][0] in 'ar':
1751
 
                self._raise_invalid(new_path, file_id,
1752
 
                    'changed entry considered not present')
 
1641
            entry = self._get_entry(0, file_id, new_path)
 
1642
            if entry[0] is None or entry[0][2] != file_id:
 
1643
                self._changes_aborted = True
 
1644
                raise errors.InconsistentDelta(new_path, file_id,
 
1645
                    'working tree does not contain new entry')
 
1646
            if (entry[1][0][0] in absent or
 
1647
                entry[1][1][0] in absent):
 
1648
                self._changes_aborted = True
 
1649
                raise errors.InconsistentDelta(new_path, file_id,
 
1650
                    'changed considered absent')
1753
1651
            entry[1][1] = new_details
1754
1652
 
1755
1653
    def _update_basis_apply_deletes(self, deletes):
1767
1665
        null = DirState.NULL_PARENT_DETAILS
1768
1666
        for old_path, new_path, file_id, _, real_delete in deletes:
1769
1667
            if real_delete != (new_path is None):
1770
 
                self._raise_invalid(old_path, file_id, "bad delete delta")
 
1668
                self._changes_aborted = True
 
1669
                raise AssertionError("bad delete delta")
1771
1670
            # the entry for this file_id must be in tree 1.
1772
1671
            dirname, basename = osutils.split(old_path)
1773
1672
            block_index, entry_index, dir_present, file_present = \
1774
1673
                self._get_block_entry_index(dirname, basename, 1)
1775
1674
            if not file_present:
1776
 
                self._raise_invalid(old_path, file_id,
 
1675
                self._changes_aborted = True
 
1676
                raise errors.InconsistentDelta(old_path, file_id,
1777
1677
                    'basis tree does not contain removed entry')
1778
1678
            entry = self._dirblocks[block_index][1][entry_index]
1779
 
            # The state of the entry in the 'active' WT
1780
 
            active_kind = entry[1][0][0]
1781
1679
            if entry[0][2] != file_id:
1782
 
                self._raise_invalid(old_path, file_id,
 
1680
                self._changes_aborted = True
 
1681
                raise errors.InconsistentDelta(old_path, file_id,
1783
1682
                    'mismatched file_id in tree 1')
1784
 
            dir_block = ()
1785
 
            old_kind = entry[1][1][0]
1786
 
            if active_kind in 'ar':
1787
 
                # The active tree doesn't have this file_id.
1788
 
                # The basis tree is changing this record. If this is a
1789
 
                # rename, then we don't want the record here at all
1790
 
                # anymore. If it is just an in-place change, we want the
1791
 
                # record here, but we'll add it if we need to. So we just
1792
 
                # delete it
1793
 
                if active_kind == 'r':
1794
 
                    active_path = entry[1][0][1]
1795
 
                    active_entry = self._get_entry(0, file_id, active_path)
1796
 
                    if active_entry[1][1][0] != 'r':
1797
 
                        self._raise_invalid(old_path, file_id,
1798
 
                            "Dirstate did not have matching rename entries")
1799
 
                    elif active_entry[1][0][0] in 'ar':
1800
 
                        self._raise_invalid(old_path, file_id,
1801
 
                            "Dirstate had a rename pointing at an inactive"
1802
 
                            " tree0")
1803
 
                    active_entry[1][1] = null
 
1683
            if real_delete:
 
1684
                if entry[1][0][0] != 'a':
 
1685
                    self._changes_aborted = True
 
1686
                    raise errors.InconsistentDelta(old_path, file_id,
 
1687
                            'This was marked as a real delete, but the WT state'
 
1688
                            ' claims that it still exists and is versioned.')
1804
1689
                del self._dirblocks[block_index][1][entry_index]
1805
 
                if old_kind == 'd':
1806
 
                    # This was a directory, and the active tree says it
1807
 
                    # doesn't exist, and now the basis tree says it doesn't
1808
 
                    # exist. Remove its dirblock if present
1809
 
                    (dir_block_index,
1810
 
                     present) = self._find_block_index_from_key(
1811
 
                        (old_path, '', ''))
1812
 
                    if present:
1813
 
                        dir_block = self._dirblocks[dir_block_index][1]
1814
 
                        if not dir_block:
1815
 
                            # This entry is empty, go ahead and just remove it
1816
 
                            del self._dirblocks[dir_block_index]
1817
1690
            else:
1818
 
                # There is still an active record, so just mark this
1819
 
                # removed.
1820
 
                entry[1][1] = null
1821
 
                block_i, entry_i, d_present, f_present = \
1822
 
                    self._get_block_entry_index(old_path, '', 1)
1823
 
                if d_present:
1824
 
                    dir_block = self._dirblocks[block_i][1]
1825
 
            for child_entry in dir_block:
1826
 
                child_basis_kind = child_entry[1][1][0]
1827
 
                if child_basis_kind not in 'ar':
1828
 
                    self._raise_invalid(old_path, file_id,
1829
 
                        "The file id was deleted but its children were "
1830
 
                        "not deleted.")
 
1691
                if entry[1][0][0] == 'a':
 
1692
                    self._changes_aborted = True
 
1693
                    raise errors.InconsistentDelta(old_path, file_id,
 
1694
                        'The entry was considered a rename, but the source path'
 
1695
                        ' is marked as absent.')
 
1696
                    # For whatever reason, we were asked to rename an entry
 
1697
                    # that was originally marked as deleted. This could be
 
1698
                    # because we are renaming the parent directory, and the WT
 
1699
                    # current state has the file marked as deleted.
 
1700
                elif entry[1][0][0] == 'r':
 
1701
                    # implement the rename
 
1702
                    del self._dirblocks[block_index][1][entry_index]
 
1703
                else:
 
1704
                    # it is being resurrected here, so blank it out temporarily.
 
1705
                    self._dirblocks[block_index][1][entry_index][1][1] = null
1831
1706
 
1832
1707
    def _after_delta_check_parents(self, parents, index):
1833
1708
        """Check that parents required by the delta are all intact.
1842
1717
            # has the right file id.
1843
1718
            entry = self._get_entry(index, file_id, dirname_utf8)
1844
1719
            if entry[1] is None:
1845
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1720
                self._changes_aborted = True
 
1721
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1846
1722
                    file_id, "This parent is not present.")
1847
1723
            # Parents of things must be directories
1848
1724
            if entry[1][index][0] != 'd':
1849
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1725
                self._changes_aborted = True
 
1726
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1850
1727
                    file_id, "This parent is not a directory.")
1851
1728
 
1852
1729
    def _observed_sha1(self, entry, sha1, stat_value,
1853
 
        _stat_to_minikind=_stat_to_minikind):
 
1730
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
1854
1731
        """Note the sha1 of a file.
1855
1732
 
1856
1733
        :param entry: The entry the sha1 is for.
1862
1739
        except KeyError:
1863
1740
            # Unhandled kind
1864
1741
            return None
 
1742
        packed_stat = _pack_stat(stat_value)
1865
1743
        if minikind == 'f':
1866
1744
            if self._cutoff_time is None:
1867
1745
                self._sha_cutoff_time()
1868
1746
            if (stat_value.st_mtime < self._cutoff_time
1869
1747
                and stat_value.st_ctime < self._cutoff_time):
1870
1748
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
1871
 
                               pack_stat(stat_value))
1872
 
                self._mark_modified([entry])
 
1749
                               packed_stat)
 
1750
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1873
1751
 
1874
1752
    def _sha_cutoff_time(self):
1875
1753
        """Return cutoff time.
1933
1811
        """Serialise the entire dirstate to a sequence of lines."""
1934
1812
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1935
1813
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1936
 
            # read what's on disk.
 
1814
            # read whats on disk.
1937
1815
            self._state_file.seek(0)
1938
1816
            return self._state_file.readlines()
1939
1817
        lines = []
1940
1818
        lines.append(self._get_parents_line(self.get_parent_ids()))
1941
1819
        lines.append(self._get_ghosts_line(self._ghosts))
1942
 
        lines.extend(self._get_entry_lines())
 
1820
        # append the root line which is special cased
 
1821
        lines.extend(map(self._entry_to_line, self._iter_entries()))
1943
1822
        return self._get_output_lines(lines)
1944
1823
 
1945
1824
    def _get_ghosts_line(self, ghost_ids):
1950
1829
        """Create a line for the state file for parents information."""
1951
1830
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1952
1831
 
1953
 
    def _get_entry_lines(self):
1954
 
        """Create lines for entries."""
1955
 
        return map(self._entry_to_line, self._iter_entries())
1956
 
 
1957
1832
    def _get_fields_to_entry(self):
1958
1833
        """Get a function which converts entry fields into a entry record.
1959
1834
 
2077
1952
            entry_index += 1
2078
1953
        return block_index, entry_index, True, False
2079
1954
 
2080
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
2081
 
                   include_deleted=False):
 
1955
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
2082
1956
        """Get the dirstate entry for path in tree tree_index.
2083
1957
 
2084
1958
        If either file_id or path is supplied, it is used as the key to lookup.
2226
2100
            executable = False
2227
2101
        else:
2228
2102
            raise Exception("can't pack %s" % inv_entry)
2229
 
        return static_tuple.StaticTuple(minikind, fingerprint, size,
2230
 
                                        executable, tree_data)
 
2103
        return (minikind, fingerprint, size, executable, tree_data)
2231
2104
 
2232
2105
    def _iter_child_entries(self, tree_index, path_utf8):
2233
2106
        """Iterate over all the entries that are children of path_utf.
2283
2156
 
2284
2157
    def _get_id_index(self):
2285
2158
        """Get an id index of self._dirblocks.
2286
 
 
 
2159
        
2287
2160
        This maps from file_id => [(directory, name, file_id)] entries where
2288
2161
        that file_id appears in one of the trees.
2289
2162
        """
2303
2176
        # such, we use a simple tuple, and do our own uniqueness checks. While
2304
2177
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2305
2178
        # cause quadratic failure.
 
2179
        # TODO: This should use StaticTuple
2306
2180
        file_id = entry_key[2]
2307
2181
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2308
2182
        if file_id not in id_index:
2348
2222
        """The number of parent entries in each record row."""
2349
2223
        return len(self._parents) - len(self._ghosts)
2350
2224
 
2351
 
    @classmethod
2352
 
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
 
2225
    @staticmethod
 
2226
    def on_file(path, sha1_provider=None):
2353
2227
        """Construct a DirState on the file at path "path".
2354
2228
 
2355
2229
        :param path: The path at which the dirstate file on disk should live.
2356
2230
        :param sha1_provider: an object meeting the SHA1Provider interface.
2357
2231
            If None, a DefaultSHA1Provider is used.
2358
 
        :param worth_saving_limit: when the exact number of hash changed
2359
 
            entries is known, only bother saving the dirstate if more than
2360
 
            this count of entries have changed. -1 means never save.
2361
2232
        :return: An unlocked DirState object, associated with the given path.
2362
2233
        """
2363
2234
        if sha1_provider is None:
2364
2235
            sha1_provider = DefaultSHA1Provider()
2365
 
        result = cls(path, sha1_provider,
2366
 
                     worth_saving_limit=worth_saving_limit)
 
2236
        result = DirState(path, sha1_provider)
2367
2237
        return result
2368
2238
 
2369
2239
    def _read_dirblocks_if_needed(self):
2427
2297
            raise errors.BzrError('missing num_entries line')
2428
2298
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2429
2299
 
2430
 
    def sha1_from_stat(self, path, stat_result):
 
2300
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
2431
2301
        """Find a sha1 given a stat lookup."""
2432
 
        return self._get_packed_stat_index().get(pack_stat(stat_result), None)
 
2302
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
2433
2303
 
2434
2304
    def _get_packed_stat_index(self):
2435
2305
        """Get a packed_stat index of self._dirblocks."""
2461
2331
            trace.mutter('Not saving DirState because '
2462
2332
                    '_changes_aborted is set.')
2463
2333
            return
2464
 
        # TODO: Since we now distinguish IN_MEMORY_MODIFIED from
2465
 
        #       IN_MEMORY_HASH_MODIFIED, we should only fail quietly if we fail
2466
 
        #       to save an IN_MEMORY_HASH_MODIFIED, and fail *noisily* if we
2467
 
        #       fail to save IN_MEMORY_MODIFIED
2468
 
        if not self._worth_saving():
2469
 
            return
 
2334
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
 
2335
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2470
2336
 
2471
 
        grabbed_write_lock = False
2472
 
        if self._lock_state != 'w':
2473
 
            grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
2474
 
            # Switch over to the new lock, as the old one may be closed.
2475
 
            # TODO: jam 20070315 We should validate the disk file has
2476
 
            #       not changed contents, since temporary_write_lock may
2477
 
            #       not be an atomic operation.
2478
 
            self._lock_token = new_lock
2479
 
            self._state_file = new_lock.f
2480
 
            if not grabbed_write_lock:
2481
 
                # We couldn't grab a write lock, so we switch back to a read one
2482
 
                return
2483
 
        try:
2484
 
            lines = self.get_lines()
2485
 
            self._state_file.seek(0)
2486
 
            self._state_file.writelines(lines)
2487
 
            self._state_file.truncate()
2488
 
            self._state_file.flush()
2489
 
            self._maybe_fdatasync()
2490
 
            self._mark_unmodified()
2491
 
        finally:
2492
 
            if grabbed_write_lock:
2493
 
                self._lock_token = self._lock_token.restore_read_lock()
2494
 
                self._state_file = self._lock_token.f
 
2337
            grabbed_write_lock = False
 
2338
            if self._lock_state != 'w':
 
2339
                grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
 
2340
                # Switch over to the new lock, as the old one may be closed.
2495
2341
                # TODO: jam 20070315 We should validate the disk file has
2496
 
                #       not changed contents. Since restore_read_lock may
2497
 
                #       not be an atomic operation.                
2498
 
 
2499
 
    def _maybe_fdatasync(self):
2500
 
        """Flush to disk if possible and if not configured off."""
2501
 
        if self._config_stack.get('dirstate.fdatasync'):
2502
 
            osutils.fdatasync(self._state_file.fileno())
2503
 
 
2504
 
    def _worth_saving(self):
2505
 
        """Is it worth saving the dirstate or not?"""
2506
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED
2507
 
            or self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2508
 
            return True
2509
 
        if self._dirblock_state == DirState.IN_MEMORY_HASH_MODIFIED:
2510
 
            if self._worth_saving_limit == -1:
2511
 
                # We never save hash changes when the limit is -1
2512
 
                return False
2513
 
            # If we're using smart saving and only a small number of
2514
 
            # entries have changed their hash, don't bother saving. John has
2515
 
            # suggested using a heuristic here based on the size of the
2516
 
            # changed files and/or tree. For now, we go with a configurable
2517
 
            # number of changes, keeping the calculation time
2518
 
            # as low overhead as possible. (This also keeps all existing
2519
 
            # tests passing as the default is 0, i.e. always save.)
2520
 
            if len(self._known_hash_changes) >= self._worth_saving_limit:
2521
 
                return True
2522
 
        return False
 
2342
                #       not changed contents. Since temporary_write_lock may
 
2343
                #       not be an atomic operation.
 
2344
                self._lock_token = new_lock
 
2345
                self._state_file = new_lock.f
 
2346
                if not grabbed_write_lock:
 
2347
                    # We couldn't grab a write lock, so we switch back to a read one
 
2348
                    return
 
2349
            try:
 
2350
                self._state_file.seek(0)
 
2351
                self._state_file.writelines(self.get_lines())
 
2352
                self._state_file.truncate()
 
2353
                self._state_file.flush()
 
2354
                self._header_state = DirState.IN_MEMORY_UNMODIFIED
 
2355
                self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
 
2356
            finally:
 
2357
                if grabbed_write_lock:
 
2358
                    self._lock_token = self._lock_token.restore_read_lock()
 
2359
                    self._state_file = self._lock_token.f
 
2360
                    # TODO: jam 20070315 We should validate the disk file has
 
2361
                    #       not changed contents. Since restore_read_lock may
 
2362
                    #       not be an atomic operation.
2523
2363
 
2524
2364
    def _set_data(self, parent_ids, dirblocks):
2525
2365
        """Set the full dirstate data in memory.
2534
2374
        """
2535
2375
        # our memory copy is now authoritative.
2536
2376
        self._dirblocks = dirblocks
2537
 
        self._mark_modified(header_modified=True)
 
2377
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2378
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2538
2379
        self._parents = list(parent_ids)
2539
2380
        self._id_index = None
2540
2381
        self._packed_stat_index = None
2560
2401
        self._make_absent(entry)
2561
2402
        self.update_minimal(('', '', new_id), 'd',
2562
2403
            path_utf8='', packed_stat=entry[1][0][4])
2563
 
        self._mark_modified()
2564
 
        # XXX: This was added by Ian, we need to make sure there
2565
 
        #      are tests for it, because it isn't in bzr.dev TRUNK
2566
 
        #      It looks like the only place it is called is in setting the root
2567
 
        #      id of the tree. So probably we never had an _id_index when we
2568
 
        #      don't even have a root yet.
2569
 
        if self._id_index is not None:
2570
 
            self._add_to_id_index(self._id_index, entry[0])
 
2404
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2571
2405
 
2572
2406
    def set_parent_trees(self, trees, ghosts):
2573
2407
        """Set the parent trees for the dirstate.
2618
2452
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2619
2453
        # how many trees do we end up with
2620
2454
        parent_count = len(parent_trees)
2621
 
        st = static_tuple.StaticTuple
2622
2455
 
2623
2456
        # one: the current tree
2624
2457
        for entry in self._iter_entries():
2641
2474
            # the suffix is from tree_index+1:parent_count+1.
2642
2475
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2643
2476
            # now stitch in all the entries from this tree
2644
 
            last_dirname = None
2645
 
            for path, entry in tree.iter_entries_by_dir():
 
2477
            for path, entry in tree.inventory.iter_entries_by_dir():
2646
2478
                # here we process each trees details for each item in the tree.
2647
2479
                # we first update any existing entries for the id at other paths,
2648
2480
                # then we either create or update the entry for the id at the
2655
2487
                file_id = entry.file_id
2656
2488
                path_utf8 = path.encode('utf8')
2657
2489
                dirname, basename = osutils.split(path_utf8)
2658
 
                if dirname == last_dirname:
2659
 
                    # Try to re-use objects as much as possible
2660
 
                    dirname = last_dirname
2661
 
                else:
2662
 
                    last_dirname = dirname
2663
 
                new_entry_key = st(dirname, basename, file_id)
 
2490
                new_entry_key = (dirname, basename, file_id)
2664
2491
                # tree index consistency: All other paths for this id in this tree
2665
2492
                # index must point to the correct path.
2666
 
                entry_keys = id_index.get(file_id, ())
2667
 
                for entry_key in entry_keys:
 
2493
                for entry_key in id_index.get(file_id, ()):
2668
2494
                    # TODO:PROFILING: It might be faster to just update
2669
2495
                    # rather than checking if we need to, and then overwrite
2670
2496
                    # the one we are located at.
2673
2499
                        # other trees, so put absent pointers there
2674
2500
                        # This is the vertical axis in the matrix, all pointing
2675
2501
                        # to the real path.
2676
 
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
2677
 
                                                            False, '')
2678
 
                # by path consistency: Insert into an existing path record
2679
 
                # (trivial), or add a new one with relocation pointers for the
2680
 
                # other tree indexes.
 
2502
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
 
2503
                # by path consistency: Insert into an existing path record (trivial), or
 
2504
                # add a new one with relocation pointers for the other tree indexes.
 
2505
                entry_keys = id_index.get(file_id, ())
2681
2506
                if new_entry_key in entry_keys:
2682
 
                    # there is already an entry where this data belongs, just
2683
 
                    # insert it.
 
2507
                    # there is already an entry where this data belongs, just insert it.
2684
2508
                    by_path[new_entry_key][tree_index] = \
2685
2509
                        self._inv_entry_to_details(entry)
2686
2510
                else:
2696
2520
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2697
2521
                        else:
2698
2522
                            # grab any one entry, use it to find the right path.
 
2523
                            # TODO: optimise this to reduce memory use in highly
 
2524
                            # fragmented situations by reusing the relocation
 
2525
                            # records.
2699
2526
                            a_key = iter(entry_keys).next()
2700
2527
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2701
 
                                # its a pointer or missing statement, use it as
2702
 
                                # is.
 
2528
                                # its a pointer or missing statement, use it as is.
2703
2529
                                new_details.append(by_path[a_key][lookup_index])
2704
2530
                            else:
2705
2531
                                # we have the right key, make a pointer to it.
2706
2532
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2707
 
                                new_details.append(st('r', real_path, 0, False,
2708
 
                                                      ''))
 
2533
                                new_details.append(('r', real_path, 0, False, ''))
2709
2534
                    new_details.append(self._inv_entry_to_details(entry))
2710
2535
                    new_details.extend(new_location_suffix)
2711
2536
                    by_path[new_entry_key] = new_details
2717
2542
        self._entries_to_current_state(new_entries)
2718
2543
        self._parents = [rev_id for rev_id, tree in trees]
2719
2544
        self._ghosts = list(ghosts)
2720
 
        self._mark_modified(header_modified=True)
 
2545
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2546
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2721
2547
        self._id_index = id_index
2722
2548
 
2723
2549
    def _sort_entries(self, entry_list):
2727
2553
        try to keep everything in sorted blocks all the time, but sometimes
2728
2554
        it's easier to sort after the fact.
2729
2555
        """
2730
 
        # When sorting, we usually have 10x more entries than directories. (69k
2731
 
        # total entries, 4k directories). So cache the results of splitting.
2732
 
        # Saving time and objects. Also, use StaticTuple to avoid putting all
2733
 
        # of these object into python's garbage collector.
2734
 
        split_dirs = {}
2735
 
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
 
2556
        def _key(entry):
2736
2557
            # sort by: directory parts, file name, file id
2737
 
            dirpath, fname, file_id = entry[0]
2738
 
            try:
2739
 
                split = _split_dirs[dirpath]
2740
 
            except KeyError:
2741
 
                split = _st.from_sequence(dirpath.split('/'))
2742
 
                _split_dirs[dirpath] = split
2743
 
            return _st(split, fname, file_id)
 
2558
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
2744
2559
        return sorted(entry_list, key=_key)
2745
2560
 
2746
2561
    def set_state_from_inventory(self, new_inv):
2871
2686
                        current_old[0][1].decode('utf8'))
2872
2687
                self._make_absent(current_old)
2873
2688
                current_old = advance(old_iterator)
2874
 
        self._mark_modified()
 
2689
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2875
2690
        self._id_index = None
2876
2691
        self._packed_stat_index = None
2877
2692
        if tracing:
2943
2758
            if update_tree_details[0][0] == 'a': # absent
2944
2759
                raise AssertionError('bad row %r' % (update_tree_details,))
2945
2760
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2946
 
        self._mark_modified()
 
2761
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2947
2762
        return last_reference
2948
2763
 
2949
2764
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2991
2806
                            # This entry has the same path (but a different id) as
2992
2807
                            # the new entry we're adding, and is present in ths
2993
2808
                            # tree.
2994
 
                            self._raise_invalid(
 
2809
                            raise errors.InconsistentDelta(
2995
2810
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2996
2811
                                "Attempt to add item at path already occupied by "
2997
2812
                                "id %r" % entry[0][2])
3118
2933
            if not present:
3119
2934
                self._dirblocks.insert(block_index, (subdir_key[0], []))
3120
2935
 
3121
 
        self._mark_modified()
 
2936
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
3122
2937
 
3123
2938
    def _maybe_remove_row(self, block, index, id_index):
3124
2939
        """Remove index if it is absent or relocated across the row.
3350
3165
 
3351
3166
 
3352
3167
def py_update_entry(state, entry, abspath, stat_value,
3353
 
                 _stat_to_minikind=DirState._stat_to_minikind):
 
3168
                 _stat_to_minikind=DirState._stat_to_minikind,
 
3169
                 _pack_stat=pack_stat):
3354
3170
    """Update the entry based on what is actually on disk.
3355
3171
 
3356
3172
    This function only calculates the sha if it needs to - if the entry is
3369
3185
    except KeyError:
3370
3186
        # Unhandled kind
3371
3187
        return None
3372
 
    packed_stat = pack_stat(stat_value)
 
3188
    packed_stat = _pack_stat(stat_value)
3373
3189
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3374
3190
     saved_executable, saved_packed_stat) = entry[1][0]
3375
3191
 
3389
3205
    # If we have gotten this far, that means that we need to actually
3390
3206
    # process this entry.
3391
3207
    link_or_sha1 = None
3392
 
    worth_saving = True
3393
3208
    if minikind == 'f':
3394
3209
        executable = state._is_executable(stat_value.st_mode,
3395
3210
                                         saved_executable)
3411
3226
        else:
3412
3227
            entry[1][0] = ('f', '', stat_value.st_size,
3413
3228
                           executable, DirState.NULLSTAT)
3414
 
            worth_saving = False
3415
3229
    elif minikind == 'd':
3416
3230
        link_or_sha1 = None
3417
3231
        entry[1][0] = ('d', '', 0, False, packed_stat)
3423
3237
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3424
3238
            state._ensure_block(block_index, entry_index,
3425
3239
                               osutils.pathjoin(entry[0][0], entry[0][1]))
3426
 
        else:
3427
 
            worth_saving = False
3428
3240
    elif minikind == 'l':
3429
 
        if saved_minikind == 'l':
3430
 
            worth_saving = False
3431
3241
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3432
3242
        if state._cutoff_time is None:
3433
3243
            state._sha_cutoff_time()
3438
3248
        else:
3439
3249
            entry[1][0] = ('l', '', stat_value.st_size,
3440
3250
                           False, DirState.NULLSTAT)
3441
 
    if worth_saving:
3442
 
        state._mark_modified([entry])
 
3251
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
3443
3252
    return link_or_sha1
3444
3253
 
3445
3254
 
3754
3563
            raise AssertionError("don't know how to compare "
3755
3564
                "source_minikind=%r, target_minikind=%r"
3756
3565
                % (source_minikind, target_minikind))
 
3566
            ## import pdb;pdb.set_trace()
3757
3567
        return None, None
3758
3568
 
3759
3569
    def __iter__(self):
4248
4058
        _bisect_path_left,
4249
4059
        _bisect_path_right,
4250
4060
        cmp_by_dirs,
4251
 
        pack_stat,
4252
4061
        ProcessEntryC as _process_entry,
4253
4062
        update_entry as update_entry,
4254
4063
        )
4260
4069
        _bisect_path_left,
4261
4070
        _bisect_path_right,
4262
4071
        cmp_by_dirs,
4263
 
        pack_stat,
4264
4072
        )
4265
4073
    # FIXME: It would be nice to be able to track moved lines so that the
4266
4074
    # corresponding python code can be moved to the _dirstate_helpers_py