~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

(vila) Fix bzrlib.tests.test_gpg.TestVerify.test_verify_revoked_signature
 with recent versions of gpg. (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2006-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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
 
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
 
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
67
73
 
68
74
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.
 
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.
92
103
 
93
104
Ordering:
94
105
 
95
 
The entries on disk and in memory are ordered according to the following keys:
 
106
The entries on disk and in memory are ordered according to the following keys::
96
107
 
97
108
    directory, as a list of components
98
109
    filename
99
110
    file-id
100
111
 
101
112
--- 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
 
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
108
122
 
109
123
PARENT ROW's are emitted for every parent that is not in the ghosts details
110
124
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
135
149
----
136
150
 
137
151
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
 
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
141
155
    is an example of this)
142
156
 
143
157
 
144
158
Locking:
 
159
 
145
160
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
146
161
 been modified, but will require that we flush/ignore cached stat-hit data
147
162
 because we won't want to restat all files on disk just because a lock was
148
163
 acquired, yet we cannot trust the data after the previous lock was released.
149
164
 
150
 
Memory representation:
 
165
Memory representation::
 
166
 
151
167
 vector of all directories, and vector of the childen ?
152
168
   i.e.
153
169
     root_entrie = (direntry for root, [parent_direntries_for_root]),
167
183
    - What's the risk of error here? Once we have the base format being processed
168
184
      we should have a net win regardless of optimality. So we are going to
169
185
      go with what seems reasonable.
 
186
 
170
187
open questions:
171
188
 
172
189
Maybe we should do a test profile of the core structure - 10K simulated
201
218
 
202
219
"""
203
220
 
 
221
from __future__ import absolute_import
 
222
 
204
223
import bisect
205
 
import binascii
206
224
import errno
207
225
import operator
208
226
import os
209
227
from stat import S_IEXEC
210
228
import stat
211
 
import struct
212
229
import sys
213
230
import time
214
231
import zlib
215
232
 
216
233
from bzrlib import (
217
234
    cache_utf8,
 
235
    config,
218
236
    debug,
219
237
    errors,
220
238
    inventory,
222
240
    osutils,
223
241
    static_tuple,
224
242
    trace,
 
243
    urlutils,
225
244
    )
226
245
 
227
246
 
232
251
ERROR_DIRECTORY = 267
233
252
 
234
253
 
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
254
class SHA1Provider(object):
269
255
    """An interface for getting sha1s of a file."""
270
256
 
355
341
    NOT_IN_MEMORY = 0
356
342
    IN_MEMORY_UNMODIFIED = 1
357
343
    IN_MEMORY_MODIFIED = 2
 
344
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
358
345
 
359
346
    # A pack_stat (the x's) that is just noise and will never match the output
360
347
    # of base64 encode.
361
348
    NULLSTAT = 'x' * 32
362
 
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
 
349
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
363
350
 
364
351
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
365
352
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
366
353
 
367
 
    def __init__(self, path, sha1_provider):
 
354
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
368
355
        """Create a  DirState object.
369
356
 
370
357
        :param path: The path at which the dirstate file on disk should live.
371
358
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
359
        :param worth_saving_limit: when the exact number of hash changed
 
360
            entries is known, only bother saving the dirstate if more than
 
361
            this count of entries have changed.
 
362
            -1 means never save hash changes, 0 means always save hash changes.
372
363
        """
373
364
        # _header_state and _dirblock_state represent the current state
374
365
        # of the dirstate metadata and the per-row data respectiely.
411
402
        # during commit.
412
403
        self._last_block_index = None
413
404
        self._last_entry_index = None
 
405
        # The set of known hash changes
 
406
        self._known_hash_changes = set()
 
407
        # How many hash changed entries can we have without saving
 
408
        self._worth_saving_limit = worth_saving_limit
 
409
        self._config_stack = config.LocationStack(urlutils.local_path_to_url(
 
410
            path))
414
411
 
415
412
    def __repr__(self):
416
413
        return "%s(%r)" % \
417
414
            (self.__class__.__name__, self._filename)
418
415
 
 
416
    def _mark_modified(self, hash_changed_entries=None, header_modified=False):
 
417
        """Mark this dirstate as modified.
 
418
 
 
419
        :param hash_changed_entries: if non-None, mark just these entries as
 
420
            having their hash modified.
 
421
        :param header_modified: mark the header modified as well, not just the
 
422
            dirblocks.
 
423
        """
 
424
        #trace.mutter_callsite(3, "modified hash entries: %s", hash_changed_entries)
 
425
        if hash_changed_entries:
 
426
            self._known_hash_changes.update([e[0] for e in hash_changed_entries])
 
427
            if self._dirblock_state in (DirState.NOT_IN_MEMORY,
 
428
                                        DirState.IN_MEMORY_UNMODIFIED):
 
429
                # If the dirstate is already marked a IN_MEMORY_MODIFIED, then
 
430
                # that takes precedence.
 
431
                self._dirblock_state = DirState.IN_MEMORY_HASH_MODIFIED
 
432
        else:
 
433
            # TODO: Since we now have a IN_MEMORY_HASH_MODIFIED state, we
 
434
            #       should fail noisily if someone tries to set
 
435
            #       IN_MEMORY_MODIFIED but we don't have a write-lock!
 
436
            # We don't know exactly what changed so disable smart saving
 
437
            self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
438
        if header_modified:
 
439
            self._header_state = DirState.IN_MEMORY_MODIFIED
 
440
 
 
441
    def _mark_unmodified(self):
 
442
        """Mark this dirstate as unmodified."""
 
443
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
 
444
        self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
 
445
        self._known_hash_changes = set()
 
446
 
419
447
    def add(self, path, file_id, kind, stat, fingerprint):
420
448
        """Add a path to be tracked.
421
449
 
547
575
        if kind == 'directory':
548
576
           # insert a new dirblock
549
577
           self._ensure_block(block_index, entry_index, utf8path)
550
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
578
        self._mark_modified()
551
579
        if self._id_index:
552
580
            self._add_to_id_index(self._id_index, entry_key)
553
581
 
1019
1047
 
1020
1048
        self._ghosts = []
1021
1049
        self._parents = [parents[0]]
1022
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1023
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1050
        self._mark_modified(header_modified=True)
1024
1051
 
1025
1052
    def _empty_parent_info(self):
1026
1053
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1155
1182
    def _fields_per_entry(self):
1156
1183
        """How many null separated fields should be in each entry row.
1157
1184
 
1158
 
        Each line now has an extra '\n' field which is not used
 
1185
        Each line now has an extra '\\n' field which is not used
1159
1186
        so we just skip over it
1160
 
        entry size:
 
1187
 
 
1188
        entry size::
1161
1189
            3 fields for the key
1162
1190
            + number of fields per tree_data (5) * tree count
1163
1191
            + newline
1264
1292
                    parent_trees.append((parent_id, parent_tree))
1265
1293
                    parent_tree.lock_read()
1266
1294
                result.set_parent_trees(parent_trees, [])
1267
 
                result.set_state_from_inventory(tree.inventory)
 
1295
                result.set_state_from_inventory(tree.root_inventory)
1268
1296
            finally:
1269
1297
                for revid, parent_tree in parent_trees:
1270
1298
                    parent_tree.unlock()
1276
1304
            raise
1277
1305
        return result
1278
1306
 
 
1307
    def _check_delta_is_valid(self, delta):
 
1308
        return list(inventory._check_delta_unique_ids(
 
1309
                    inventory._check_delta_unique_old_paths(
 
1310
                    inventory._check_delta_unique_new_paths(
 
1311
                    inventory._check_delta_ids_match_entry(
 
1312
                    inventory._check_delta_ids_are_valid(
 
1313
                    inventory._check_delta_new_path_entry_both_or_None(delta)))))))
 
1314
 
1279
1315
    def update_by_delta(self, delta):
1280
1316
        """Apply an inventory delta to the dirstate for tree 0
1281
1317
 
1299
1335
        new_ids = set()
1300
1336
        # This loop transforms the delta to single atomic operations that can
1301
1337
        # be executed and validated.
1302
 
        for old_path, new_path, file_id, inv_entry in sorted(
1303
 
            inventory._check_delta_unique_old_paths(
1304
 
            inventory._check_delta_unique_new_paths(
1305
 
            inventory._check_delta_ids_match_entry(
1306
 
            inventory._check_delta_ids_are_valid(
1307
 
            inventory._check_delta_new_path_entry_both_or_None(delta))))),
1308
 
            reverse=True):
 
1338
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1339
        for old_path, new_path, file_id, inv_entry in delta:
1309
1340
            if (file_id in insertions) or (file_id in removals):
1310
 
                raise errors.InconsistentDelta(old_path or new_path, file_id,
 
1341
                self._raise_invalid(old_path or new_path, file_id,
1311
1342
                    "repeated file_id")
1312
1343
            if old_path is not None:
1313
1344
                old_path = old_path.encode('utf-8')
1316
1347
                new_ids.add(file_id)
1317
1348
            if new_path is not None:
1318
1349
                if inv_entry is None:
1319
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1350
                    self._raise_invalid(new_path, file_id,
1320
1351
                        "new_path with no entry")
1321
1352
                new_path = new_path.encode('utf-8')
1322
1353
                dirname_utf8, basename = osutils.split(new_path)
1363
1394
            # _get_entry raises BzrError when a request is inconsistent; we
1364
1395
            # want such errors to be shown as InconsistentDelta - and that 
1365
1396
            # fits the behaviour we trigger.
1366
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1397
            raise errors.InconsistentDeltaDelta(delta,
 
1398
                "error from _get_entry. %s" % (e,))
1367
1399
 
1368
1400
    def _apply_removals(self, removals):
1369
1401
        for file_id, path in sorted(removals, reverse=True,
1374
1406
            try:
1375
1407
                entry = self._dirblocks[block_i][1][entry_i]
1376
1408
            except IndexError:
1377
 
                self._changes_aborted = True
1378
 
                raise errors.InconsistentDelta(path, file_id,
 
1409
                self._raise_invalid(path, file_id,
1379
1410
                    "Wrong path for old path.")
1380
1411
            if not f_present or entry[1][0][0] in 'ar':
1381
 
                self._changes_aborted = True
1382
 
                raise errors.InconsistentDelta(path, file_id,
 
1412
                self._raise_invalid(path, file_id,
1383
1413
                    "Wrong path for old path.")
1384
1414
            if file_id != entry[0][2]:
1385
 
                self._changes_aborted = True
1386
 
                raise errors.InconsistentDelta(path, file_id,
 
1415
                self._raise_invalid(path, file_id,
1387
1416
                    "Attempt to remove path has wrong id - found %r."
1388
1417
                    % entry[0][2])
1389
1418
            self._make_absent(entry)
1399
1428
                # be due to it being in a parent tree, or a corrupt delta.
1400
1429
                for child_entry in self._dirblocks[block_i][1]:
1401
1430
                    if child_entry[1][0][0] not in ('r', 'a'):
1402
 
                        self._changes_aborted = True
1403
 
                        raise errors.InconsistentDelta(path, entry[0][2],
 
1431
                        self._raise_invalid(path, entry[0][2],
1404
1432
                            "The file id was deleted but its children were "
1405
1433
                            "not deleted.")
1406
1434
 
1410
1438
                self.update_minimal(key, minikind, executable, fingerprint,
1411
1439
                                    path_utf8=path_utf8)
1412
1440
        except errors.NotVersionedError:
1413
 
            self._changes_aborted = True
1414
 
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
 
1441
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
1415
1442
                "Missing parent")
1416
1443
 
1417
1444
    def update_basis_by_delta(self, delta, new_revid):
1425
1452
        Note that an exception during the operation of this method will leave
1426
1453
        the dirstate in a corrupt state where it should not be saved.
1427
1454
 
1428
 
        Finally, we expect all changes to be synchronising the basis tree with
1429
 
        the working tree.
1430
 
 
1431
1455
        :param new_revid: The new revision id for the trees parent.
1432
1456
        :param delta: An inventory delta (see apply_inventory_delta) describing
1433
1457
            the changes from the current left most parent revision to new_revid.
1445
1469
 
1446
1470
        self._parents[0] = new_revid
1447
1471
 
1448
 
        delta = sorted(delta, reverse=True)
 
1472
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1449
1473
        adds = []
1450
1474
        changes = []
1451
1475
        deletes = []
1472
1496
        new_ids = set()
1473
1497
        for old_path, new_path, file_id, inv_entry in delta:
1474
1498
            if inv_entry is not None and file_id != inv_entry.file_id:
1475
 
                raise errors.InconsistentDelta(new_path, file_id,
 
1499
                self._raise_invalid(new_path, file_id,
1476
1500
                    "mismatched entry file_id %r" % inv_entry)
1477
 
            if new_path is not None:
 
1501
            if new_path is None:
 
1502
                new_path_utf8 = None
 
1503
            else:
1478
1504
                if inv_entry is None:
1479
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1505
                    self._raise_invalid(new_path, file_id,
1480
1506
                        "new_path with no entry")
1481
1507
                new_path_utf8 = encode(new_path)
1482
1508
                # note the parent for validation
1484
1510
                if basename_utf8:
1485
1511
                    parents.add((dirname_utf8, inv_entry.parent_id))
1486
1512
            if old_path is None:
1487
 
                adds.append((None, encode(new_path), file_id,
 
1513
                old_path_utf8 = None
 
1514
            else:
 
1515
                old_path_utf8 = encode(old_path)
 
1516
            if old_path is None:
 
1517
                adds.append((None, new_path_utf8, file_id,
1488
1518
                    inv_to_entry(inv_entry), True))
1489
1519
                new_ids.add(file_id)
1490
1520
            elif new_path is None:
1491
 
                deletes.append((encode(old_path), None, file_id, None, True))
1492
 
            elif (old_path, new_path) != root_only:
 
1521
                deletes.append((old_path_utf8, None, file_id, None, True))
 
1522
            elif (old_path, new_path) == root_only:
 
1523
                # change things in-place
 
1524
                # Note: the case of a parent directory changing its file_id
 
1525
                #       tends to break optimizations here, because officially
 
1526
                #       the file has actually been moved, it just happens to
 
1527
                #       end up at the same path. If we can figure out how to
 
1528
                #       handle that case, we can avoid a lot of add+delete
 
1529
                #       pairs for objects that stay put.
 
1530
                # elif old_path == new_path:
 
1531
                changes.append((old_path_utf8, new_path_utf8, file_id,
 
1532
                                inv_to_entry(inv_entry)))
 
1533
            else:
1493
1534
                # Renames:
1494
1535
                # Because renames must preserve their children we must have
1495
1536
                # processed all relocations and removes before hand. The sort
1505
1546
                self._update_basis_apply_deletes(deletes)
1506
1547
                deletes = []
1507
1548
                # Split into an add/delete pair recursively.
1508
 
                adds.append((None, new_path_utf8, file_id,
1509
 
                    inv_to_entry(inv_entry), False))
 
1549
                adds.append((old_path_utf8, new_path_utf8, file_id,
 
1550
                             inv_to_entry(inv_entry), False))
1510
1551
                # Expunge deletes that we've seen so that deleted/renamed
1511
1552
                # children of a rename directory are handled correctly.
1512
 
                new_deletes = reversed(list(self._iter_child_entries(1,
1513
 
                    encode(old_path))))
 
1553
                new_deletes = reversed(list(
 
1554
                    self._iter_child_entries(1, old_path_utf8)))
1514
1555
                # Remove the current contents of the tree at orig_path, and
1515
1556
                # reinsert at the correct new path.
1516
1557
                for entry in new_deletes:
1517
 
                    if entry[0][0]:
1518
 
                        source_path = entry[0][0] + '/' + entry[0][1]
 
1558
                    child_dirname, child_basename, child_file_id = entry[0]
 
1559
                    if child_dirname:
 
1560
                        source_path = child_dirname + '/' + child_basename
1519
1561
                    else:
1520
 
                        source_path = entry[0][1]
 
1562
                        source_path = child_basename
1521
1563
                    if new_path_utf8:
1522
 
                        target_path = new_path_utf8 + source_path[len(old_path):]
 
1564
                        target_path = \
 
1565
                            new_path_utf8 + source_path[len(old_path_utf8):]
1523
1566
                    else:
1524
 
                        if old_path == '':
 
1567
                        if old_path_utf8 == '':
1525
1568
                            raise AssertionError("cannot rename directory to"
1526
 
                                " itself")
1527
 
                        target_path = source_path[len(old_path) + 1:]
 
1569
                                                 " itself")
 
1570
                        target_path = source_path[len(old_path_utf8) + 1:]
1528
1571
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1529
1572
                    deletes.append(
1530
1573
                        (source_path, target_path, entry[0][2], None, False))
1531
1574
                deletes.append(
1532
 
                    (encode(old_path), new_path, file_id, None, False))
1533
 
            else:
1534
 
                # changes to just the root should not require remove/insertion
1535
 
                # of everything.
1536
 
                changes.append((encode(old_path), encode(new_path), file_id,
1537
 
                    inv_to_entry(inv_entry)))
 
1575
                    (old_path_utf8, new_path_utf8, file_id, None, False))
 
1576
 
1538
1577
        self._check_delta_ids_absent(new_ids, delta, 1)
1539
1578
        try:
1540
1579
            # Finish expunging deletes/first half of renames.
1550
1589
            if 'integrity error' not in str(e):
1551
1590
                raise
1552
1591
            # _get_entry raises BzrError when a request is inconsistent; we
1553
 
            # want such errors to be shown as InconsistentDelta - and that 
1554
 
            # fits the behaviour we trigger. Partof this is driven by dirstate
1555
 
            # only supporting deltas that turn the basis into a closer fit to
1556
 
            # the active tree.
1557
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1592
            # want such errors to be shown as InconsistentDelta - and that
 
1593
            # fits the behaviour we trigger.
 
1594
            raise errors.InconsistentDeltaDelta(delta,
 
1595
                "error from _get_entry. %s" % (e,))
1558
1596
 
1559
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1560
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1597
        self._mark_modified(header_modified=True)
1561
1598
        self._id_index = None
1562
1599
        return
1563
1600
 
1577
1614
                if entry[0][2] != file_id:
1578
1615
                    # Different file_id, so not what we want.
1579
1616
                    continue
1580
 
                # NB: No changes made before this helper is called, so no need
1581
 
                # to set the _changes_aborted flag.
1582
 
                raise errors.InconsistentDelta(
1583
 
                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
 
1617
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
1584
1618
                    "This file_id is new in the delta but already present in "
1585
1619
                    "the target")
1586
1620
 
 
1621
    def _raise_invalid(self, path, file_id, reason):
 
1622
        self._changes_aborted = True
 
1623
        raise errors.InconsistentDelta(path, file_id, reason)
 
1624
 
1587
1625
    def _update_basis_apply_adds(self, adds):
1588
1626
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1589
1627
 
1597
1635
        """
1598
1636
        # Adds are accumulated partly from renames, so can be in any input
1599
1637
        # order - sort it.
1600
 
        adds.sort()
 
1638
        # TODO: we may want to sort in dirblocks order. That way each entry
 
1639
        #       will end up in the same directory, allowing the _get_entry
 
1640
        #       fast-path for looking up 2 items in the same dir work.
 
1641
        adds.sort(key=lambda x: x[1])
1601
1642
        # adds is now in lexographic order, which places all parents before
1602
1643
        # their children, so we can process it linearly.
1603
1644
        absent = 'ar'
 
1645
        st = static_tuple.StaticTuple
1604
1646
        for old_path, new_path, file_id, new_details, real_add in adds:
1605
 
            # the entry for this file_id must be in tree 0.
1606
 
            entry = self._get_entry(0, file_id, new_path)
1607
 
            if entry[0] is None or entry[0][2] != file_id:
1608
 
                self._changes_aborted = True
1609
 
                raise errors.InconsistentDelta(new_path, file_id,
1610
 
                    'working tree does not contain new entry')
1611
 
            if real_add and entry[1][1][0] not in absent:
1612
 
                self._changes_aborted = True
1613
 
                raise errors.InconsistentDelta(new_path, file_id,
1614
 
                    'The entry was considered to be a genuinely new record,'
1615
 
                    ' but there was already an old record for it.')
1616
 
            # We don't need to update the target of an 'r' because the handling
1617
 
            # of renames turns all 'r' situations into a delete at the original
1618
 
            # location.
1619
 
            entry[1][1] = new_details
 
1647
            dirname, basename = osutils.split(new_path)
 
1648
            entry_key = st(dirname, basename, file_id)
 
1649
            block_index, present = self._find_block_index_from_key(entry_key)
 
1650
            if not present:
 
1651
                # The block where we want to put the file is not present.
 
1652
                # However, it might have just been an empty directory. Look for
 
1653
                # the parent in the basis-so-far before throwing an error.
 
1654
                parent_dir, parent_base = osutils.split(dirname)
 
1655
                parent_block_idx, parent_entry_idx, _, parent_present = \
 
1656
                    self._get_block_entry_index(parent_dir, parent_base, 1)
 
1657
                if not parent_present:
 
1658
                    self._raise_invalid(new_path, file_id,
 
1659
                        "Unable to find block for this record."
 
1660
                        " Was the parent added?")
 
1661
                self._ensure_block(parent_block_idx, parent_entry_idx, dirname)
 
1662
 
 
1663
            block = self._dirblocks[block_index][1]
 
1664
            entry_index, present = self._find_entry_index(entry_key, block)
 
1665
            if real_add:
 
1666
                if old_path is not None:
 
1667
                    self._raise_invalid(new_path, file_id,
 
1668
                        'considered a real add but still had old_path at %s'
 
1669
                        % (old_path,))
 
1670
            if present:
 
1671
                entry = block[entry_index]
 
1672
                basis_kind = entry[1][1][0]
 
1673
                if basis_kind == 'a':
 
1674
                    entry[1][1] = new_details
 
1675
                elif basis_kind == 'r':
 
1676
                    raise NotImplementedError()
 
1677
                else:
 
1678
                    self._raise_invalid(new_path, file_id,
 
1679
                        "An entry was marked as a new add"
 
1680
                        " but the basis target already existed")
 
1681
            else:
 
1682
                # The exact key was not found in the block. However, we need to
 
1683
                # check if there is a key next to us that would have matched.
 
1684
                # We only need to check 2 locations, because there are only 2
 
1685
                # trees present.
 
1686
                for maybe_index in range(entry_index-1, entry_index+1):
 
1687
                    if maybe_index < 0 or maybe_index >= len(block):
 
1688
                        continue
 
1689
                    maybe_entry = block[maybe_index]
 
1690
                    if maybe_entry[0][:2] != (dirname, basename):
 
1691
                        # Just a random neighbor
 
1692
                        continue
 
1693
                    if maybe_entry[0][2] == file_id:
 
1694
                        raise AssertionError(
 
1695
                            '_find_entry_index didnt find a key match'
 
1696
                            ' but walking the data did, for %s'
 
1697
                            % (entry_key,))
 
1698
                    basis_kind = maybe_entry[1][1][0]
 
1699
                    if basis_kind not in 'ar':
 
1700
                        self._raise_invalid(new_path, file_id,
 
1701
                            "we have an add record for path, but the path"
 
1702
                            " is already present with another file_id %s"
 
1703
                            % (maybe_entry[0][2],))
 
1704
 
 
1705
                entry = (entry_key, [DirState.NULL_PARENT_DETAILS,
 
1706
                                     new_details])
 
1707
                block.insert(entry_index, entry)
 
1708
 
 
1709
            active_kind = entry[1][0][0]
 
1710
            if active_kind == 'a':
 
1711
                # The active record shows up as absent, this could be genuine,
 
1712
                # or it could be present at some other location. We need to
 
1713
                # verify.
 
1714
                id_index = self._get_id_index()
 
1715
                # The id_index may not be perfectly accurate for tree1, because
 
1716
                # we haven't been keeping it updated. However, it should be
 
1717
                # fine for tree0, and that gives us enough info for what we
 
1718
                # need
 
1719
                keys = id_index.get(file_id, ())
 
1720
                for key in keys:
 
1721
                    block_i, entry_i, d_present, f_present = \
 
1722
                        self._get_block_entry_index(key[0], key[1], 0)
 
1723
                    if not f_present:
 
1724
                        continue
 
1725
                    active_entry = self._dirblocks[block_i][1][entry_i]
 
1726
                    if (active_entry[0][2] != file_id):
 
1727
                        # Some other file is at this path, we don't need to
 
1728
                        # link it.
 
1729
                        continue
 
1730
                    real_active_kind = active_entry[1][0][0]
 
1731
                    if real_active_kind in 'ar':
 
1732
                        # We found a record, which was not *this* record,
 
1733
                        # which matches the file_id, but is not actually
 
1734
                        # present. Something seems *really* wrong.
 
1735
                        self._raise_invalid(new_path, file_id,
 
1736
                            "We found a tree0 entry that doesnt make sense")
 
1737
                    # Now, we've found a tree0 entry which matches the file_id
 
1738
                    # but is at a different location. So update them to be
 
1739
                    # rename records.
 
1740
                    active_dir, active_name = active_entry[0][:2]
 
1741
                    if active_dir:
 
1742
                        active_path = active_dir + '/' + active_name
 
1743
                    else:
 
1744
                        active_path = active_name
 
1745
                    active_entry[1][1] = st('r', new_path, 0, False, '')
 
1746
                    entry[1][0] = st('r', active_path, 0, False, '')
 
1747
            elif active_kind == 'r':
 
1748
                raise NotImplementedError()
 
1749
 
 
1750
            new_kind = new_details[0]
 
1751
            if new_kind == 'd':
 
1752
                self._ensure_block(block_index, entry_index, new_path)
1620
1753
 
1621
1754
    def _update_basis_apply_changes(self, changes):
1622
1755
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1627
1760
        absent = 'ar'
1628
1761
        for old_path, new_path, file_id, new_details in changes:
1629
1762
            # the entry for this file_id must be in tree 0.
1630
 
            entry = self._get_entry(0, file_id, new_path)
1631
 
            if entry[0] is None or entry[0][2] != file_id:
1632
 
                self._changes_aborted = True
1633
 
                raise errors.InconsistentDelta(new_path, file_id,
1634
 
                    'working tree does not contain new entry')
1635
 
            if (entry[1][0][0] in absent or
1636
 
                entry[1][1][0] in absent):
1637
 
                self._changes_aborted = True
1638
 
                raise errors.InconsistentDelta(new_path, file_id,
1639
 
                    'changed considered absent')
 
1763
            entry = self._get_entry(1, file_id, new_path)
 
1764
            if entry[0] is None or entry[1][1][0] in 'ar':
 
1765
                self._raise_invalid(new_path, file_id,
 
1766
                    'changed entry considered not present')
1640
1767
            entry[1][1] = new_details
1641
1768
 
1642
1769
    def _update_basis_apply_deletes(self, deletes):
1654
1781
        null = DirState.NULL_PARENT_DETAILS
1655
1782
        for old_path, new_path, file_id, _, real_delete in deletes:
1656
1783
            if real_delete != (new_path is None):
1657
 
                self._changes_aborted = True
1658
 
                raise AssertionError("bad delete delta")
 
1784
                self._raise_invalid(old_path, file_id, "bad delete delta")
1659
1785
            # the entry for this file_id must be in tree 1.
1660
1786
            dirname, basename = osutils.split(old_path)
1661
1787
            block_index, entry_index, dir_present, file_present = \
1662
1788
                self._get_block_entry_index(dirname, basename, 1)
1663
1789
            if not file_present:
1664
 
                self._changes_aborted = True
1665
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1790
                self._raise_invalid(old_path, file_id,
1666
1791
                    'basis tree does not contain removed entry')
1667
1792
            entry = self._dirblocks[block_index][1][entry_index]
 
1793
            # The state of the entry in the 'active' WT
 
1794
            active_kind = entry[1][0][0]
1668
1795
            if entry[0][2] != file_id:
1669
 
                self._changes_aborted = True
1670
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1796
                self._raise_invalid(old_path, file_id,
1671
1797
                    'mismatched file_id in tree 1')
1672
 
            if real_delete:
1673
 
                if entry[1][0][0] != 'a':
1674
 
                    self._changes_aborted = True
1675
 
                    raise errors.InconsistentDelta(old_path, file_id,
1676
 
                            'This was marked as a real delete, but the WT state'
1677
 
                            ' claims that it still exists and is versioned.')
 
1798
            dir_block = ()
 
1799
            old_kind = entry[1][1][0]
 
1800
            if active_kind in 'ar':
 
1801
                # The active tree doesn't have this file_id.
 
1802
                # The basis tree is changing this record. If this is a
 
1803
                # rename, then we don't want the record here at all
 
1804
                # anymore. If it is just an in-place change, we want the
 
1805
                # record here, but we'll add it if we need to. So we just
 
1806
                # delete it
 
1807
                if active_kind == 'r':
 
1808
                    active_path = entry[1][0][1]
 
1809
                    active_entry = self._get_entry(0, file_id, active_path)
 
1810
                    if active_entry[1][1][0] != 'r':
 
1811
                        self._raise_invalid(old_path, file_id,
 
1812
                            "Dirstate did not have matching rename entries")
 
1813
                    elif active_entry[1][0][0] in 'ar':
 
1814
                        self._raise_invalid(old_path, file_id,
 
1815
                            "Dirstate had a rename pointing at an inactive"
 
1816
                            " tree0")
 
1817
                    active_entry[1][1] = null
1678
1818
                del self._dirblocks[block_index][1][entry_index]
 
1819
                if old_kind == 'd':
 
1820
                    # This was a directory, and the active tree says it
 
1821
                    # doesn't exist, and now the basis tree says it doesn't
 
1822
                    # exist. Remove its dirblock if present
 
1823
                    (dir_block_index,
 
1824
                     present) = self._find_block_index_from_key(
 
1825
                        (old_path, '', ''))
 
1826
                    if present:
 
1827
                        dir_block = self._dirblocks[dir_block_index][1]
 
1828
                        if not dir_block:
 
1829
                            # This entry is empty, go ahead and just remove it
 
1830
                            del self._dirblocks[dir_block_index]
1679
1831
            else:
1680
 
                if entry[1][0][0] == 'a':
1681
 
                    self._changes_aborted = True
1682
 
                    raise errors.InconsistentDelta(old_path, file_id,
1683
 
                        'The entry was considered a rename, but the source path'
1684
 
                        ' is marked as absent.')
1685
 
                    # For whatever reason, we were asked to rename an entry
1686
 
                    # that was originally marked as deleted. This could be
1687
 
                    # because we are renaming the parent directory, and the WT
1688
 
                    # current state has the file marked as deleted.
1689
 
                elif entry[1][0][0] == 'r':
1690
 
                    # implement the rename
1691
 
                    del self._dirblocks[block_index][1][entry_index]
1692
 
                else:
1693
 
                    # it is being resurrected here, so blank it out temporarily.
1694
 
                    self._dirblocks[block_index][1][entry_index][1][1] = null
 
1832
                # There is still an active record, so just mark this
 
1833
                # removed.
 
1834
                entry[1][1] = null
 
1835
                block_i, entry_i, d_present, f_present = \
 
1836
                    self._get_block_entry_index(old_path, '', 1)
 
1837
                if d_present:
 
1838
                    dir_block = self._dirblocks[block_i][1]
 
1839
            for child_entry in dir_block:
 
1840
                child_basis_kind = child_entry[1][1][0]
 
1841
                if child_basis_kind not in 'ar':
 
1842
                    self._raise_invalid(old_path, file_id,
 
1843
                        "The file id was deleted but its children were "
 
1844
                        "not deleted.")
1695
1845
 
1696
1846
    def _after_delta_check_parents(self, parents, index):
1697
1847
        """Check that parents required by the delta are all intact.
1706
1856
            # has the right file id.
1707
1857
            entry = self._get_entry(index, file_id, dirname_utf8)
1708
1858
            if entry[1] is None:
1709
 
                self._changes_aborted = True
1710
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1859
                self._raise_invalid(dirname_utf8.decode('utf8'),
1711
1860
                    file_id, "This parent is not present.")
1712
1861
            # Parents of things must be directories
1713
1862
            if entry[1][index][0] != 'd':
1714
 
                self._changes_aborted = True
1715
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1863
                self._raise_invalid(dirname_utf8.decode('utf8'),
1716
1864
                    file_id, "This parent is not a directory.")
1717
1865
 
1718
1866
    def _observed_sha1(self, entry, sha1, stat_value,
1719
 
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
 
1867
        _stat_to_minikind=_stat_to_minikind):
1720
1868
        """Note the sha1 of a file.
1721
1869
 
1722
1870
        :param entry: The entry the sha1 is for.
1728
1876
        except KeyError:
1729
1877
            # Unhandled kind
1730
1878
            return None
1731
 
        packed_stat = _pack_stat(stat_value)
1732
1879
        if minikind == 'f':
1733
1880
            if self._cutoff_time is None:
1734
1881
                self._sha_cutoff_time()
1735
1882
            if (stat_value.st_mtime < self._cutoff_time
1736
1883
                and stat_value.st_ctime < self._cutoff_time):
1737
 
                entry[1][0] = ('f', sha1, entry[1][0][2], entry[1][0][3],
1738
 
                    packed_stat)
1739
 
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1884
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
 
1885
                               pack_stat(stat_value))
 
1886
                self._mark_modified([entry])
1740
1887
 
1741
1888
    def _sha_cutoff_time(self):
1742
1889
        """Return cutoff time.
1786
1933
            # paths are produced by UnicodeDirReader on purpose.
1787
1934
            abspath = abspath.encode(fs_encoding)
1788
1935
        target = os.readlink(abspath)
1789
 
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
 
1936
        if fs_encoding not in ('utf-8', 'ascii'):
1790
1937
            # Change encoding if needed
1791
1938
            target = target.decode(fs_encoding).encode('UTF-8')
1792
1939
        return target
1800
1947
        """Serialise the entire dirstate to a sequence of lines."""
1801
1948
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1802
1949
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1803
 
            # read whats on disk.
 
1950
            # read what's on disk.
1804
1951
            self._state_file.seek(0)
1805
1952
            return self._state_file.readlines()
1806
1953
        lines = []
1807
1954
        lines.append(self._get_parents_line(self.get_parent_ids()))
1808
1955
        lines.append(self._get_ghosts_line(self._ghosts))
1809
 
        # append the root line which is special cased
1810
 
        lines.extend(map(self._entry_to_line, self._iter_entries()))
 
1956
        lines.extend(self._get_entry_lines())
1811
1957
        return self._get_output_lines(lines)
1812
1958
 
1813
1959
    def _get_ghosts_line(self, ghost_ids):
1818
1964
        """Create a line for the state file for parents information."""
1819
1965
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1820
1966
 
 
1967
    def _get_entry_lines(self):
 
1968
        """Create lines for entries."""
 
1969
        return map(self._entry_to_line, self._iter_entries())
 
1970
 
1821
1971
    def _get_fields_to_entry(self):
1822
1972
        """Get a function which converts entry fields into a entry record.
1823
1973
 
1941
2091
            entry_index += 1
1942
2092
        return block_index, entry_index, True, False
1943
2093
 
1944
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
2094
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
 
2095
                   include_deleted=False):
1945
2096
        """Get the dirstate entry for path in tree tree_index.
1946
2097
 
1947
2098
        If either file_id or path is supplied, it is used as the key to lookup.
2089
2240
            executable = False
2090
2241
        else:
2091
2242
            raise Exception("can't pack %s" % inv_entry)
2092
 
        return (minikind, fingerprint, size, executable, tree_data)
 
2243
        return static_tuple.StaticTuple(minikind, fingerprint, size,
 
2244
                                        executable, tree_data)
2093
2245
 
2094
2246
    def _iter_child_entries(self, tree_index, path_utf8):
2095
2247
        """Iterate over all the entries that are children of path_utf.
2145
2297
 
2146
2298
    def _get_id_index(self):
2147
2299
        """Get an id index of self._dirblocks.
2148
 
        
 
2300
 
2149
2301
        This maps from file_id => [(directory, name, file_id)] entries where
2150
2302
        that file_id appears in one of the trees.
2151
2303
        """
2165
2317
        # such, we use a simple tuple, and do our own uniqueness checks. While
2166
2318
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2167
2319
        # cause quadratic failure.
2168
 
        # TODO: This should use StaticTuple
2169
2320
        file_id = entry_key[2]
2170
2321
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2171
2322
        if file_id not in id_index:
2211
2362
        """The number of parent entries in each record row."""
2212
2363
        return len(self._parents) - len(self._ghosts)
2213
2364
 
2214
 
    @staticmethod
2215
 
    def on_file(path, sha1_provider=None):
 
2365
    @classmethod
 
2366
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
2216
2367
        """Construct a DirState on the file at path "path".
2217
2368
 
2218
2369
        :param path: The path at which the dirstate file on disk should live.
2219
2370
        :param sha1_provider: an object meeting the SHA1Provider interface.
2220
2371
            If None, a DefaultSHA1Provider is used.
 
2372
        :param worth_saving_limit: when the exact number of hash changed
 
2373
            entries is known, only bother saving the dirstate if more than
 
2374
            this count of entries have changed. -1 means never save.
2221
2375
        :return: An unlocked DirState object, associated with the given path.
2222
2376
        """
2223
2377
        if sha1_provider is None:
2224
2378
            sha1_provider = DefaultSHA1Provider()
2225
 
        result = DirState(path, sha1_provider)
 
2379
        result = cls(path, sha1_provider,
 
2380
                     worth_saving_limit=worth_saving_limit)
2226
2381
        return result
2227
2382
 
2228
2383
    def _read_dirblocks_if_needed(self):
2286
2441
            raise errors.BzrError('missing num_entries line')
2287
2442
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2288
2443
 
2289
 
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
 
2444
    def sha1_from_stat(self, path, stat_result):
2290
2445
        """Find a sha1 given a stat lookup."""
2291
 
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
 
2446
        return self._get_packed_stat_index().get(pack_stat(stat_result), None)
2292
2447
 
2293
2448
    def _get_packed_stat_index(self):
2294
2449
        """Get a packed_stat index of self._dirblocks."""
2320
2475
            trace.mutter('Not saving DirState because '
2321
2476
                    '_changes_aborted is set.')
2322
2477
            return
2323
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2324
 
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
2478
        # TODO: Since we now distinguish IN_MEMORY_MODIFIED from
 
2479
        #       IN_MEMORY_HASH_MODIFIED, we should only fail quietly if we fail
 
2480
        #       to save an IN_MEMORY_HASH_MODIFIED, and fail *noisily* if we
 
2481
        #       fail to save IN_MEMORY_MODIFIED
 
2482
        if not self._worth_saving():
 
2483
            return
2325
2484
 
2326
 
            grabbed_write_lock = False
2327
 
            if self._lock_state != 'w':
2328
 
                grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
2329
 
                # Switch over to the new lock, as the old one may be closed.
 
2485
        grabbed_write_lock = False
 
2486
        if self._lock_state != 'w':
 
2487
            grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
 
2488
            # Switch over to the new lock, as the old one may be closed.
 
2489
            # TODO: jam 20070315 We should validate the disk file has
 
2490
            #       not changed contents, since temporary_write_lock may
 
2491
            #       not be an atomic operation.
 
2492
            self._lock_token = new_lock
 
2493
            self._state_file = new_lock.f
 
2494
            if not grabbed_write_lock:
 
2495
                # We couldn't grab a write lock, so we switch back to a read one
 
2496
                return
 
2497
        try:
 
2498
            lines = self.get_lines()
 
2499
            self._state_file.seek(0)
 
2500
            self._state_file.writelines(lines)
 
2501
            self._state_file.truncate()
 
2502
            self._state_file.flush()
 
2503
            self._maybe_fdatasync()
 
2504
            self._mark_unmodified()
 
2505
        finally:
 
2506
            if grabbed_write_lock:
 
2507
                self._lock_token = self._lock_token.restore_read_lock()
 
2508
                self._state_file = self._lock_token.f
2330
2509
                # TODO: jam 20070315 We should validate the disk file has
2331
 
                #       not changed contents. Since temporary_write_lock may
2332
 
                #       not be an atomic operation.
2333
 
                self._lock_token = new_lock
2334
 
                self._state_file = new_lock.f
2335
 
                if not grabbed_write_lock:
2336
 
                    # We couldn't grab a write lock, so we switch back to a read one
2337
 
                    return
2338
 
            try:
2339
 
                self._state_file.seek(0)
2340
 
                self._state_file.writelines(self.get_lines())
2341
 
                self._state_file.truncate()
2342
 
                self._state_file.flush()
2343
 
                self._header_state = DirState.IN_MEMORY_UNMODIFIED
2344
 
                self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
2345
 
            finally:
2346
 
                if grabbed_write_lock:
2347
 
                    self._lock_token = self._lock_token.restore_read_lock()
2348
 
                    self._state_file = self._lock_token.f
2349
 
                    # TODO: jam 20070315 We should validate the disk file has
2350
 
                    #       not changed contents. Since restore_read_lock may
2351
 
                    #       not be an atomic operation.
 
2510
                #       not changed contents. Since restore_read_lock may
 
2511
                #       not be an atomic operation.                
 
2512
 
 
2513
    def _maybe_fdatasync(self):
 
2514
        """Flush to disk if possible and if not configured off."""
 
2515
        if self._config_stack.get('dirstate.fdatasync'):
 
2516
            osutils.fdatasync(self._state_file.fileno())
 
2517
 
 
2518
    def _worth_saving(self):
 
2519
        """Is it worth saving the dirstate or not?"""
 
2520
        if (self._header_state == DirState.IN_MEMORY_MODIFIED
 
2521
            or self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
2522
            return True
 
2523
        if self._dirblock_state == DirState.IN_MEMORY_HASH_MODIFIED:
 
2524
            if self._worth_saving_limit == -1:
 
2525
                # We never save hash changes when the limit is -1
 
2526
                return False
 
2527
            # If we're using smart saving and only a small number of
 
2528
            # entries have changed their hash, don't bother saving. John has
 
2529
            # suggested using a heuristic here based on the size of the
 
2530
            # changed files and/or tree. For now, we go with a configurable
 
2531
            # number of changes, keeping the calculation time
 
2532
            # as low overhead as possible. (This also keeps all existing
 
2533
            # tests passing as the default is 0, i.e. always save.)
 
2534
            if len(self._known_hash_changes) >= self._worth_saving_limit:
 
2535
                return True
 
2536
        return False
2352
2537
 
2353
2538
    def _set_data(self, parent_ids, dirblocks):
2354
2539
        """Set the full dirstate data in memory.
2363
2548
        """
2364
2549
        # our memory copy is now authoritative.
2365
2550
        self._dirblocks = dirblocks
2366
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2367
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2551
        self._mark_modified(header_modified=True)
2368
2552
        self._parents = list(parent_ids)
2369
2553
        self._id_index = None
2370
2554
        self._packed_stat_index = None
2390
2574
        self._make_absent(entry)
2391
2575
        self.update_minimal(('', '', new_id), 'd',
2392
2576
            path_utf8='', packed_stat=entry[1][0][4])
2393
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2577
        self._mark_modified()
2394
2578
 
2395
2579
    def set_parent_trees(self, trees, ghosts):
2396
2580
        """Set the parent trees for the dirstate.
2441
2625
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2442
2626
        # how many trees do we end up with
2443
2627
        parent_count = len(parent_trees)
 
2628
        st = static_tuple.StaticTuple
2444
2629
 
2445
2630
        # one: the current tree
2446
2631
        for entry in self._iter_entries():
2463
2648
            # the suffix is from tree_index+1:parent_count+1.
2464
2649
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2465
2650
            # now stitch in all the entries from this tree
2466
 
            for path, entry in tree.inventory.iter_entries_by_dir():
 
2651
            last_dirname = None
 
2652
            for path, entry in tree.iter_entries_by_dir():
2467
2653
                # here we process each trees details for each item in the tree.
2468
2654
                # we first update any existing entries for the id at other paths,
2469
2655
                # then we either create or update the entry for the id at the
2476
2662
                file_id = entry.file_id
2477
2663
                path_utf8 = path.encode('utf8')
2478
2664
                dirname, basename = osutils.split(path_utf8)
2479
 
                new_entry_key = (dirname, basename, file_id)
 
2665
                if dirname == last_dirname:
 
2666
                    # Try to re-use objects as much as possible
 
2667
                    dirname = last_dirname
 
2668
                else:
 
2669
                    last_dirname = dirname
 
2670
                new_entry_key = st(dirname, basename, file_id)
2480
2671
                # tree index consistency: All other paths for this id in this tree
2481
2672
                # index must point to the correct path.
2482
 
                for entry_key in id_index.get(file_id, ()):
 
2673
                entry_keys = id_index.get(file_id, ())
 
2674
                for entry_key in entry_keys:
2483
2675
                    # TODO:PROFILING: It might be faster to just update
2484
2676
                    # rather than checking if we need to, and then overwrite
2485
2677
                    # the one we are located at.
2488
2680
                        # other trees, so put absent pointers there
2489
2681
                        # This is the vertical axis in the matrix, all pointing
2490
2682
                        # to the real path.
2491
 
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2492
 
                # by path consistency: Insert into an existing path record (trivial), or
2493
 
                # add a new one with relocation pointers for the other tree indexes.
2494
 
                entry_keys = id_index.get(file_id, ())
 
2683
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
 
2684
                                                            False, '')
 
2685
                # by path consistency: Insert into an existing path record
 
2686
                # (trivial), or add a new one with relocation pointers for the
 
2687
                # other tree indexes.
2495
2688
                if new_entry_key in entry_keys:
2496
 
                    # there is already an entry where this data belongs, just insert it.
 
2689
                    # there is already an entry where this data belongs, just
 
2690
                    # insert it.
2497
2691
                    by_path[new_entry_key][tree_index] = \
2498
2692
                        self._inv_entry_to_details(entry)
2499
2693
                else:
2509
2703
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2510
2704
                        else:
2511
2705
                            # grab any one entry, use it to find the right path.
2512
 
                            # TODO: optimise this to reduce memory use in highly
2513
 
                            # fragmented situations by reusing the relocation
2514
 
                            # records.
2515
2706
                            a_key = iter(entry_keys).next()
2516
2707
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2517
 
                                # its a pointer or missing statement, use it as is.
 
2708
                                # its a pointer or missing statement, use it as
 
2709
                                # is.
2518
2710
                                new_details.append(by_path[a_key][lookup_index])
2519
2711
                            else:
2520
2712
                                # we have the right key, make a pointer to it.
2521
2713
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2522
 
                                new_details.append(('r', real_path, 0, False, ''))
 
2714
                                new_details.append(st('r', real_path, 0, False,
 
2715
                                                      ''))
2523
2716
                    new_details.append(self._inv_entry_to_details(entry))
2524
2717
                    new_details.extend(new_location_suffix)
2525
2718
                    by_path[new_entry_key] = new_details
2531
2724
        self._entries_to_current_state(new_entries)
2532
2725
        self._parents = [rev_id for rev_id, tree in trees]
2533
2726
        self._ghosts = list(ghosts)
2534
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2535
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2727
        self._mark_modified(header_modified=True)
2536
2728
        self._id_index = id_index
2537
2729
 
2538
2730
    def _sort_entries(self, entry_list):
2542
2734
        try to keep everything in sorted blocks all the time, but sometimes
2543
2735
        it's easier to sort after the fact.
2544
2736
        """
2545
 
        def _key(entry):
 
2737
        # When sorting, we usually have 10x more entries than directories. (69k
 
2738
        # total entries, 4k directories). So cache the results of splitting.
 
2739
        # Saving time and objects. Also, use StaticTuple to avoid putting all
 
2740
        # of these object into python's garbage collector.
 
2741
        split_dirs = {}
 
2742
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
2546
2743
            # sort by: directory parts, file name, file id
2547
 
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
 
2744
            dirpath, fname, file_id = entry[0]
 
2745
            try:
 
2746
                split = _split_dirs[dirpath]
 
2747
            except KeyError:
 
2748
                split = _st.from_sequence(dirpath.split('/'))
 
2749
                _split_dirs[dirpath] = split
 
2750
            return _st(split, fname, file_id)
2548
2751
        return sorted(entry_list, key=_key)
2549
2752
 
2550
2753
    def set_state_from_inventory(self, new_inv):
2675
2878
                        current_old[0][1].decode('utf8'))
2676
2879
                self._make_absent(current_old)
2677
2880
                current_old = advance(old_iterator)
2678
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2881
        self._mark_modified()
2679
2882
        self._id_index = None
2680
2883
        self._packed_stat_index = None
2681
2884
        if tracing:
2682
2885
            trace.mutter("set_state_from_inventory complete.")
2683
2886
 
 
2887
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
 
2888
        """Wipe the currently stored state and set it to something new.
 
2889
 
 
2890
        This is a hard-reset for the data we are working with.
 
2891
        """
 
2892
        # Technically, we really want a write lock, but until we write, we
 
2893
        # don't really need it.
 
2894
        self._requires_lock()
 
2895
        # root dir and root dir contents with no children. We have to have a
 
2896
        # root for set_state_from_inventory to work correctly.
 
2897
        empty_root = (('', '', inventory.ROOT_ID),
 
2898
                      [('d', '', 0, False, DirState.NULLSTAT)])
 
2899
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
 
2900
        self._set_data([], empty_tree_dirblocks)
 
2901
        self.set_state_from_inventory(working_inv)
 
2902
        self.set_parent_trees(parent_trees, parent_ghosts)
 
2903
 
2684
2904
    def _make_absent(self, current_old):
2685
2905
        """Mark current_old - an entry - as absent for tree 0.
2686
2906
 
2730
2950
            if update_tree_details[0][0] == 'a': # absent
2731
2951
                raise AssertionError('bad row %r' % (update_tree_details,))
2732
2952
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2733
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2953
        self._mark_modified()
2734
2954
        return last_reference
2735
2955
 
2736
2956
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2778
2998
                            # This entry has the same path (but a different id) as
2779
2999
                            # the new entry we're adding, and is present in ths
2780
3000
                            # tree.
2781
 
                            raise errors.InconsistentDelta(
 
3001
                            self._raise_invalid(
2782
3002
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2783
3003
                                "Attempt to add item at path already occupied by "
2784
3004
                                "id %r" % entry[0][2])
2876
3096
            # converted to relocated.
2877
3097
            if path_utf8 is None:
2878
3098
                raise AssertionError('no path')
2879
 
            existing_keys = id_index[key[2]]
 
3099
            existing_keys = id_index.get(key[2], ())
2880
3100
            if key not in existing_keys:
2881
3101
                raise AssertionError('We found the entry in the blocks, but'
2882
3102
                    ' the key is not in the id_index.'
2883
3103
                    ' key: %s, existing_keys: %s' % (key, existing_keys))
2884
 
            for entry_key in id_index[key[2]]:
 
3104
            for entry_key in existing_keys:
2885
3105
                # TODO:PROFILING: It might be faster to just update
2886
3106
                # rather than checking if we need to, and then overwrite
2887
3107
                # the one we are located at.
2905
3125
            if not present:
2906
3126
                self._dirblocks.insert(block_index, (subdir_key[0], []))
2907
3127
 
2908
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3128
        self._mark_modified()
2909
3129
 
2910
3130
    def _maybe_remove_row(self, block, index, id_index):
2911
3131
        """Remove index if it is absent or relocated across the row.
3067
3287
        if self._id_index is not None:
3068
3288
            for file_id, entry_keys in self._id_index.iteritems():
3069
3289
                for entry_key in entry_keys:
 
3290
                    # Check that the entry in the map is pointing to the same
 
3291
                    # file_id
3070
3292
                    if entry_key[2] != file_id:
3071
3293
                        raise AssertionError(
3072
3294
                            'file_id %r did not match entry key %s'
3073
3295
                            % (file_id, entry_key))
 
3296
                    # And that from this entry key, we can look up the original
 
3297
                    # record
 
3298
                    block_index, present = self._find_block_index_from_key(entry_key)
 
3299
                    if not present:
 
3300
                        raise AssertionError('missing block for entry key: %r', entry_key)
 
3301
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
 
3302
                    if not present:
 
3303
                        raise AssertionError('missing entry for key: %r', entry_key)
3074
3304
                if len(entry_keys) != len(set(entry_keys)):
3075
3305
                    raise AssertionError(
3076
3306
                        'id_index contained non-unique data for %s'
3137
3367
 
3138
3368
 
3139
3369
def py_update_entry(state, entry, abspath, stat_value,
3140
 
                 _stat_to_minikind=DirState._stat_to_minikind,
3141
 
                 _pack_stat=pack_stat):
 
3370
                 _stat_to_minikind=DirState._stat_to_minikind):
3142
3371
    """Update the entry based on what is actually on disk.
3143
3372
 
3144
3373
    This function only calculates the sha if it needs to - if the entry is
3157
3386
    except KeyError:
3158
3387
        # Unhandled kind
3159
3388
        return None
3160
 
    packed_stat = _pack_stat(stat_value)
 
3389
    packed_stat = pack_stat(stat_value)
3161
3390
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3162
3391
     saved_executable, saved_packed_stat) = entry[1][0]
3163
3392
 
3177
3406
    # If we have gotten this far, that means that we need to actually
3178
3407
    # process this entry.
3179
3408
    link_or_sha1 = None
 
3409
    worth_saving = True
3180
3410
    if minikind == 'f':
3181
3411
        executable = state._is_executable(stat_value.st_mode,
3182
3412
                                         saved_executable)
3198
3428
        else:
3199
3429
            entry[1][0] = ('f', '', stat_value.st_size,
3200
3430
                           executable, DirState.NULLSTAT)
 
3431
            worth_saving = False
3201
3432
    elif minikind == 'd':
3202
3433
        link_or_sha1 = None
3203
3434
        entry[1][0] = ('d', '', 0, False, packed_stat)
3209
3440
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3210
3441
            state._ensure_block(block_index, entry_index,
3211
3442
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
3443
        else:
 
3444
            worth_saving = False
3212
3445
    elif minikind == 'l':
 
3446
        if saved_minikind == 'l':
 
3447
            worth_saving = False
3213
3448
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3214
3449
        if state._cutoff_time is None:
3215
3450
            state._sha_cutoff_time()
3220
3455
        else:
3221
3456
            entry[1][0] = ('l', '', stat_value.st_size,
3222
3457
                           False, DirState.NULLSTAT)
3223
 
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3458
    if worth_saving:
 
3459
        state._mark_modified([entry])
3224
3460
    return link_or_sha1
3225
3461
 
3226
3462
 
3535
3771
            raise AssertionError("don't know how to compare "
3536
3772
                "source_minikind=%r, target_minikind=%r"
3537
3773
                % (source_minikind, target_minikind))
3538
 
            ## import pdb;pdb.set_trace()
3539
3774
        return None, None
3540
3775
 
3541
3776
    def __iter__(self):
4030
4265
        _bisect_path_left,
4031
4266
        _bisect_path_right,
4032
4267
        cmp_by_dirs,
 
4268
        pack_stat,
4033
4269
        ProcessEntryC as _process_entry,
4034
4270
        update_entry as update_entry,
4035
4271
        )
4041
4277
        _bisect_path_left,
4042
4278
        _bisect_path_right,
4043
4279
        cmp_by_dirs,
 
4280
        pack_stat,
4044
4281
        )
4045
4282
    # FIXME: It would be nice to be able to track moved lines so that the
4046
4283
    # corresponding python code can be moved to the _dirstate_helpers_py