~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

merge bzr.dev.

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
202
219
"""
203
220
 
204
221
import bisect
205
 
import binascii
206
222
import errno
207
223
import operator
208
224
import os
209
225
from stat import S_IEXEC
210
226
import stat
211
 
import struct
212
227
import sys
213
228
import time
214
229
import zlib
215
230
 
216
231
from bzrlib import (
217
232
    cache_utf8,
 
233
    config,
218
234
    debug,
219
235
    errors,
220
236
    inventory,
222
238
    osutils,
223
239
    static_tuple,
224
240
    trace,
 
241
    urlutils,
225
242
    )
226
243
 
227
244
 
232
249
ERROR_DIRECTORY = 267
233
250
 
234
251
 
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
252
class SHA1Provider(object):
269
253
    """An interface for getting sha1s of a file."""
270
254
 
355
339
    NOT_IN_MEMORY = 0
356
340
    IN_MEMORY_UNMODIFIED = 1
357
341
    IN_MEMORY_MODIFIED = 2
 
342
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
358
343
 
359
344
    # A pack_stat (the x's) that is just noise and will never match the output
360
345
    # of base64 encode.
361
346
    NULLSTAT = 'x' * 32
362
 
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
 
347
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
363
348
 
364
349
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
365
350
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
366
351
 
367
 
    def __init__(self, path, sha1_provider):
 
352
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
368
353
        """Create a  DirState object.
369
354
 
370
355
        :param path: The path at which the dirstate file on disk should live.
371
356
        :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.
372
361
        """
373
362
        # _header_state and _dirblock_state represent the current state
374
363
        # of the dirstate metadata and the per-row data respectiely.
411
400
        # during commit.
412
401
        self._last_block_index = None
413
402
        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))
414
409
 
415
410
    def __repr__(self):
416
411
        return "%s(%r)" % \
417
412
            (self.__class__.__name__, self._filename)
418
413
 
 
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
 
419
445
    def add(self, path, file_id, kind, stat, fingerprint):
420
446
        """Add a path to be tracked.
421
447
 
547
573
        if kind == 'directory':
548
574
           # insert a new dirblock
549
575
           self._ensure_block(block_index, entry_index, utf8path)
550
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
576
        self._mark_modified()
551
577
        if self._id_index:
552
578
            self._add_to_id_index(self._id_index, entry_key)
553
579
 
1019
1045
 
1020
1046
        self._ghosts = []
1021
1047
        self._parents = [parents[0]]
1022
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1023
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1048
        self._mark_modified(header_modified=True)
1024
1049
 
1025
1050
    def _empty_parent_info(self):
1026
1051
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1155
1180
    def _fields_per_entry(self):
1156
1181
        """How many null separated fields should be in each entry row.
1157
1182
 
1158
 
        Each line now has an extra '\n' field which is not used
 
1183
        Each line now has an extra '\\n' field which is not used
1159
1184
        so we just skip over it
1160
 
        entry size:
 
1185
 
 
1186
        entry size::
1161
1187
            3 fields for the key
1162
1188
            + number of fields per tree_data (5) * tree count
1163
1189
            + newline
1276
1302
            raise
1277
1303
        return result
1278
1304
 
 
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
 
1279
1313
    def update_by_delta(self, delta):
1280
1314
        """Apply an inventory delta to the dirstate for tree 0
1281
1315
 
1299
1333
        new_ids = set()
1300
1334
        # This loop transforms the delta to single atomic operations that can
1301
1335
        # 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):
 
1336
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1337
        for old_path, new_path, file_id, inv_entry in delta:
1309
1338
            if (file_id in insertions) or (file_id in removals):
1310
 
                raise errors.InconsistentDelta(old_path or new_path, file_id,
 
1339
                self._raise_invalid(old_path or new_path, file_id,
1311
1340
                    "repeated file_id")
1312
1341
            if old_path is not None:
1313
1342
                old_path = old_path.encode('utf-8')
1316
1345
                new_ids.add(file_id)
1317
1346
            if new_path is not None:
1318
1347
                if inv_entry is None:
1319
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1348
                    self._raise_invalid(new_path, file_id,
1320
1349
                        "new_path with no entry")
1321
1350
                new_path = new_path.encode('utf-8')
1322
1351
                dirname_utf8, basename = osutils.split(new_path)
1363
1392
            # _get_entry raises BzrError when a request is inconsistent; we
1364
1393
            # want such errors to be shown as InconsistentDelta - and that 
1365
1394
            # fits the behaviour we trigger.
1366
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1395
            raise errors.InconsistentDeltaDelta(delta,
 
1396
                "error from _get_entry. %s" % (e,))
1367
1397
 
1368
1398
    def _apply_removals(self, removals):
1369
1399
        for file_id, path in sorted(removals, reverse=True,
1374
1404
            try:
1375
1405
                entry = self._dirblocks[block_i][1][entry_i]
1376
1406
            except IndexError:
1377
 
                self._changes_aborted = True
1378
 
                raise errors.InconsistentDelta(path, file_id,
 
1407
                self._raise_invalid(path, file_id,
1379
1408
                    "Wrong path for old path.")
1380
1409
            if not f_present or entry[1][0][0] in 'ar':
1381
 
                self._changes_aborted = True
1382
 
                raise errors.InconsistentDelta(path, file_id,
 
1410
                self._raise_invalid(path, file_id,
1383
1411
                    "Wrong path for old path.")
1384
1412
            if file_id != entry[0][2]:
1385
 
                self._changes_aborted = True
1386
 
                raise errors.InconsistentDelta(path, file_id,
 
1413
                self._raise_invalid(path, file_id,
1387
1414
                    "Attempt to remove path has wrong id - found %r."
1388
1415
                    % entry[0][2])
1389
1416
            self._make_absent(entry)
1399
1426
                # be due to it being in a parent tree, or a corrupt delta.
1400
1427
                for child_entry in self._dirblocks[block_i][1]:
1401
1428
                    if child_entry[1][0][0] not in ('r', 'a'):
1402
 
                        self._changes_aborted = True
1403
 
                        raise errors.InconsistentDelta(path, entry[0][2],
 
1429
                        self._raise_invalid(path, entry[0][2],
1404
1430
                            "The file id was deleted but its children were "
1405
1431
                            "not deleted.")
1406
1432
 
1410
1436
                self.update_minimal(key, minikind, executable, fingerprint,
1411
1437
                                    path_utf8=path_utf8)
1412
1438
        except errors.NotVersionedError:
1413
 
            self._changes_aborted = True
1414
 
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
 
1439
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
1415
1440
                "Missing parent")
1416
1441
 
1417
1442
    def update_basis_by_delta(self, delta, new_revid):
1425
1450
        Note that an exception during the operation of this method will leave
1426
1451
        the dirstate in a corrupt state where it should not be saved.
1427
1452
 
1428
 
        Finally, we expect all changes to be synchronising the basis tree with
1429
 
        the working tree.
1430
 
 
1431
1453
        :param new_revid: The new revision id for the trees parent.
1432
1454
        :param delta: An inventory delta (see apply_inventory_delta) describing
1433
1455
            the changes from the current left most parent revision to new_revid.
1445
1467
 
1446
1468
        self._parents[0] = new_revid
1447
1469
 
1448
 
        delta = sorted(delta, reverse=True)
 
1470
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1449
1471
        adds = []
1450
1472
        changes = []
1451
1473
        deletes = []
1472
1494
        new_ids = set()
1473
1495
        for old_path, new_path, file_id, inv_entry in delta:
1474
1496
            if inv_entry is not None and file_id != inv_entry.file_id:
1475
 
                raise errors.InconsistentDelta(new_path, file_id,
 
1497
                self._raise_invalid(new_path, file_id,
1476
1498
                    "mismatched entry file_id %r" % inv_entry)
1477
 
            if new_path is not None:
 
1499
            if new_path is None:
 
1500
                new_path_utf8 = None
 
1501
            else:
1478
1502
                if inv_entry is None:
1479
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1503
                    self._raise_invalid(new_path, file_id,
1480
1504
                        "new_path with no entry")
1481
1505
                new_path_utf8 = encode(new_path)
1482
1506
                # note the parent for validation
1484
1508
                if basename_utf8:
1485
1509
                    parents.add((dirname_utf8, inv_entry.parent_id))
1486
1510
            if old_path is None:
1487
 
                adds.append((None, encode(new_path), file_id,
 
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,
1488
1516
                    inv_to_entry(inv_entry), True))
1489
1517
                new_ids.add(file_id)
1490
1518
            elif new_path is None:
1491
 
                deletes.append((encode(old_path), None, file_id, None, True))
1492
 
            elif (old_path, new_path) != root_only:
 
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:
1493
1532
                # Renames:
1494
1533
                # Because renames must preserve their children we must have
1495
1534
                # processed all relocations and removes before hand. The sort
1505
1544
                self._update_basis_apply_deletes(deletes)
1506
1545
                deletes = []
1507
1546
                # Split into an add/delete pair recursively.
1508
 
                adds.append((None, new_path_utf8, file_id,
1509
 
                    inv_to_entry(inv_entry), False))
 
1547
                adds.append((old_path_utf8, new_path_utf8, file_id,
 
1548
                             inv_to_entry(inv_entry), False))
1510
1549
                # Expunge deletes that we've seen so that deleted/renamed
1511
1550
                # children of a rename directory are handled correctly.
1512
 
                new_deletes = reversed(list(self._iter_child_entries(1,
1513
 
                    encode(old_path))))
 
1551
                new_deletes = reversed(list(
 
1552
                    self._iter_child_entries(1, old_path_utf8)))
1514
1553
                # Remove the current contents of the tree at orig_path, and
1515
1554
                # reinsert at the correct new path.
1516
1555
                for entry in new_deletes:
1517
 
                    if entry[0][0]:
1518
 
                        source_path = entry[0][0] + '/' + entry[0][1]
 
1556
                    child_dirname, child_basename, child_file_id = entry[0]
 
1557
                    if child_dirname:
 
1558
                        source_path = child_dirname + '/' + child_basename
1519
1559
                    else:
1520
 
                        source_path = entry[0][1]
 
1560
                        source_path = child_basename
1521
1561
                    if new_path_utf8:
1522
1562
                        target_path = new_path_utf8 + source_path[len(old_path):]
1523
1563
                    else:
1524
1564
                        if old_path == '':
1525
1565
                            raise AssertionError("cannot rename directory to"
1526
 
                                " itself")
 
1566
                                                 " itself")
1527
1567
                        target_path = source_path[len(old_path) + 1:]
1528
1568
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1529
1569
                    deletes.append(
1530
1570
                        (source_path, target_path, entry[0][2], None, False))
1531
 
                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)))
 
1571
                deletes.append((old_path_utf8, new_path, file_id, None, False))
1538
1572
        self._check_delta_ids_absent(new_ids, delta, 1)
1539
1573
        try:
1540
1574
            # Finish expunging deletes/first half of renames.
1550
1584
            if 'integrity error' not in str(e):
1551
1585
                raise
1552
1586
            # _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.")
 
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,))
1558
1591
 
1559
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1560
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1592
        self._mark_modified(header_modified=True)
1561
1593
        self._id_index = None
1562
1594
        return
1563
1595
 
1577
1609
                if entry[0][2] != file_id:
1578
1610
                    # Different file_id, so not what we want.
1579
1611
                    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,
 
1612
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
1584
1613
                    "This file_id is new in the delta but already present in "
1585
1614
                    "the target")
1586
1615
 
 
1616
    def _raise_invalid(self, path, file_id, reason):
 
1617
        self._changes_aborted = True
 
1618
        raise errors.InconsistentDelta(path, file_id, reason)
 
1619
 
1587
1620
    def _update_basis_apply_adds(self, adds):
1588
1621
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1589
1622
 
1597
1630
        """
1598
1631
        # Adds are accumulated partly from renames, so can be in any input
1599
1632
        # order - sort it.
1600
 
        adds.sort()
 
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])
1601
1637
        # adds is now in lexographic order, which places all parents before
1602
1638
        # their children, so we can process it linearly.
1603
1639
        absent = 'ar'
 
1640
        st = static_tuple.StaticTuple
1604
1641
        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
 
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)
1620
1739
 
1621
1740
    def _update_basis_apply_changes(self, changes):
1622
1741
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1627
1746
        absent = 'ar'
1628
1747
        for old_path, new_path, file_id, new_details in changes:
1629
1748
            # 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')
 
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')
1640
1753
            entry[1][1] = new_details
1641
1754
 
1642
1755
    def _update_basis_apply_deletes(self, deletes):
1654
1767
        null = DirState.NULL_PARENT_DETAILS
1655
1768
        for old_path, new_path, file_id, _, real_delete in deletes:
1656
1769
            if real_delete != (new_path is None):
1657
 
                self._changes_aborted = True
1658
 
                raise AssertionError("bad delete delta")
 
1770
                self._raise_invalid(old_path, file_id, "bad delete delta")
1659
1771
            # the entry for this file_id must be in tree 1.
1660
1772
            dirname, basename = osutils.split(old_path)
1661
1773
            block_index, entry_index, dir_present, file_present = \
1662
1774
                self._get_block_entry_index(dirname, basename, 1)
1663
1775
            if not file_present:
1664
 
                self._changes_aborted = True
1665
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1776
                self._raise_invalid(old_path, file_id,
1666
1777
                    'basis tree does not contain removed entry')
1667
1778
            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]
1668
1781
            if entry[0][2] != file_id:
1669
 
                self._changes_aborted = True
1670
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1782
                self._raise_invalid(old_path, file_id,
1671
1783
                    '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.')
 
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
1678
1804
                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]
1679
1817
            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
 
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.")
1695
1831
 
1696
1832
    def _after_delta_check_parents(self, parents, index):
1697
1833
        """Check that parents required by the delta are all intact.
1706
1842
            # has the right file id.
1707
1843
            entry = self._get_entry(index, file_id, dirname_utf8)
1708
1844
            if entry[1] is None:
1709
 
                self._changes_aborted = True
1710
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1845
                self._raise_invalid(dirname_utf8.decode('utf8'),
1711
1846
                    file_id, "This parent is not present.")
1712
1847
            # Parents of things must be directories
1713
1848
            if entry[1][index][0] != 'd':
1714
 
                self._changes_aborted = True
1715
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1849
                self._raise_invalid(dirname_utf8.decode('utf8'),
1716
1850
                    file_id, "This parent is not a directory.")
1717
1851
 
1718
1852
    def _observed_sha1(self, entry, sha1, stat_value,
1719
 
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
 
1853
        _stat_to_minikind=_stat_to_minikind):
1720
1854
        """Note the sha1 of a file.
1721
1855
 
1722
1856
        :param entry: The entry the sha1 is for.
1728
1862
        except KeyError:
1729
1863
            # Unhandled kind
1730
1864
            return None
1731
 
        packed_stat = _pack_stat(stat_value)
1732
1865
        if minikind == 'f':
1733
1866
            if self._cutoff_time is None:
1734
1867
                self._sha_cutoff_time()
1735
1868
            if (stat_value.st_mtime < self._cutoff_time
1736
1869
                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
 
1870
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
 
1871
                               pack_stat(stat_value))
 
1872
                self._mark_modified([entry])
1740
1873
 
1741
1874
    def _sha_cutoff_time(self):
1742
1875
        """Return cutoff time.
1800
1933
        """Serialise the entire dirstate to a sequence of lines."""
1801
1934
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1802
1935
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1803
 
            # read whats on disk.
 
1936
            # read what's on disk.
1804
1937
            self._state_file.seek(0)
1805
1938
            return self._state_file.readlines()
1806
1939
        lines = []
1807
1940
        lines.append(self._get_parents_line(self.get_parent_ids()))
1808
1941
        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()))
 
1942
        lines.extend(self._get_entry_lines())
1811
1943
        return self._get_output_lines(lines)
1812
1944
 
1813
1945
    def _get_ghosts_line(self, ghost_ids):
1818
1950
        """Create a line for the state file for parents information."""
1819
1951
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1820
1952
 
 
1953
    def _get_entry_lines(self):
 
1954
        """Create lines for entries."""
 
1955
        return map(self._entry_to_line, self._iter_entries())
 
1956
 
1821
1957
    def _get_fields_to_entry(self):
1822
1958
        """Get a function which converts entry fields into a entry record.
1823
1959
 
1941
2077
            entry_index += 1
1942
2078
        return block_index, entry_index, True, False
1943
2079
 
1944
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
2080
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
 
2081
                   include_deleted=False):
1945
2082
        """Get the dirstate entry for path in tree tree_index.
1946
2083
 
1947
2084
        If either file_id or path is supplied, it is used as the key to lookup.
2089
2226
            executable = False
2090
2227
        else:
2091
2228
            raise Exception("can't pack %s" % inv_entry)
2092
 
        return (minikind, fingerprint, size, executable, tree_data)
 
2229
        return static_tuple.StaticTuple(minikind, fingerprint, size,
 
2230
                                        executable, tree_data)
2093
2231
 
2094
2232
    def _iter_child_entries(self, tree_index, path_utf8):
2095
2233
        """Iterate over all the entries that are children of path_utf.
2145
2283
 
2146
2284
    def _get_id_index(self):
2147
2285
        """Get an id index of self._dirblocks.
2148
 
        
 
2286
 
2149
2287
        This maps from file_id => [(directory, name, file_id)] entries where
2150
2288
        that file_id appears in one of the trees.
2151
2289
        """
2165
2303
        # such, we use a simple tuple, and do our own uniqueness checks. While
2166
2304
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2167
2305
        # cause quadratic failure.
2168
 
        # TODO: This should use StaticTuple
2169
2306
        file_id = entry_key[2]
2170
2307
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2171
2308
        if file_id not in id_index:
2211
2348
        """The number of parent entries in each record row."""
2212
2349
        return len(self._parents) - len(self._ghosts)
2213
2350
 
2214
 
    @staticmethod
2215
 
    def on_file(path, sha1_provider=None):
 
2351
    @classmethod
 
2352
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
2216
2353
        """Construct a DirState on the file at path "path".
2217
2354
 
2218
2355
        :param path: The path at which the dirstate file on disk should live.
2219
2356
        :param sha1_provider: an object meeting the SHA1Provider interface.
2220
2357
            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.
2221
2361
        :return: An unlocked DirState object, associated with the given path.
2222
2362
        """
2223
2363
        if sha1_provider is None:
2224
2364
            sha1_provider = DefaultSHA1Provider()
2225
 
        result = DirState(path, sha1_provider)
 
2365
        result = cls(path, sha1_provider,
 
2366
                     worth_saving_limit=worth_saving_limit)
2226
2367
        return result
2227
2368
 
2228
2369
    def _read_dirblocks_if_needed(self):
2286
2427
            raise errors.BzrError('missing num_entries line')
2287
2428
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2288
2429
 
2289
 
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
 
2430
    def sha1_from_stat(self, path, stat_result):
2290
2431
        """Find a sha1 given a stat lookup."""
2291
 
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
 
2432
        return self._get_packed_stat_index().get(pack_stat(stat_result), None)
2292
2433
 
2293
2434
    def _get_packed_stat_index(self):
2294
2435
        """Get a packed_stat index of self._dirblocks."""
2320
2461
            trace.mutter('Not saving DirState because '
2321
2462
                    '_changes_aborted is set.')
2322
2463
            return
2323
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2324
 
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
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
2325
2470
 
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.
 
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
2330
2495
                # 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.
 
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
2352
2523
 
2353
2524
    def _set_data(self, parent_ids, dirblocks):
2354
2525
        """Set the full dirstate data in memory.
2363
2534
        """
2364
2535
        # our memory copy is now authoritative.
2365
2536
        self._dirblocks = dirblocks
2366
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2367
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2537
        self._mark_modified(header_modified=True)
2368
2538
        self._parents = list(parent_ids)
2369
2539
        self._id_index = None
2370
2540
        self._packed_stat_index = None
2390
2560
        self._make_absent(entry)
2391
2561
        self.update_minimal(('', '', new_id), 'd',
2392
2562
            path_utf8='', packed_stat=entry[1][0][4])
2393
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
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])
2394
2571
 
2395
2572
    def set_parent_trees(self, trees, ghosts):
2396
2573
        """Set the parent trees for the dirstate.
2441
2618
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2442
2619
        # how many trees do we end up with
2443
2620
        parent_count = len(parent_trees)
 
2621
        st = static_tuple.StaticTuple
2444
2622
 
2445
2623
        # one: the current tree
2446
2624
        for entry in self._iter_entries():
2463
2641
            # the suffix is from tree_index+1:parent_count+1.
2464
2642
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2465
2643
            # now stitch in all the entries from this tree
2466
 
            for path, entry in tree.inventory.iter_entries_by_dir():
 
2644
            last_dirname = None
 
2645
            for path, entry in tree.iter_entries_by_dir():
2467
2646
                # here we process each trees details for each item in the tree.
2468
2647
                # we first update any existing entries for the id at other paths,
2469
2648
                # then we either create or update the entry for the id at the
2476
2655
                file_id = entry.file_id
2477
2656
                path_utf8 = path.encode('utf8')
2478
2657
                dirname, basename = osutils.split(path_utf8)
2479
 
                new_entry_key = (dirname, basename, file_id)
 
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)
2480
2664
                # tree index consistency: All other paths for this id in this tree
2481
2665
                # index must point to the correct path.
2482
 
                for entry_key in id_index.get(file_id, ()):
 
2666
                entry_keys = id_index.get(file_id, ())
 
2667
                for entry_key in entry_keys:
2483
2668
                    # TODO:PROFILING: It might be faster to just update
2484
2669
                    # rather than checking if we need to, and then overwrite
2485
2670
                    # the one we are located at.
2488
2673
                        # other trees, so put absent pointers there
2489
2674
                        # This is the vertical axis in the matrix, all pointing
2490
2675
                        # 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, ())
 
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.
2495
2681
                if new_entry_key in entry_keys:
2496
 
                    # there is already an entry where this data belongs, just insert it.
 
2682
                    # there is already an entry where this data belongs, just
 
2683
                    # insert it.
2497
2684
                    by_path[new_entry_key][tree_index] = \
2498
2685
                        self._inv_entry_to_details(entry)
2499
2686
                else:
2509
2696
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2510
2697
                        else:
2511
2698
                            # 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
2699
                            a_key = iter(entry_keys).next()
2516
2700
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2517
 
                                # its a pointer or missing statement, use it as is.
 
2701
                                # its a pointer or missing statement, use it as
 
2702
                                # is.
2518
2703
                                new_details.append(by_path[a_key][lookup_index])
2519
2704
                            else:
2520
2705
                                # we have the right key, make a pointer to it.
2521
2706
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2522
 
                                new_details.append(('r', real_path, 0, False, ''))
 
2707
                                new_details.append(st('r', real_path, 0, False,
 
2708
                                                      ''))
2523
2709
                    new_details.append(self._inv_entry_to_details(entry))
2524
2710
                    new_details.extend(new_location_suffix)
2525
2711
                    by_path[new_entry_key] = new_details
2531
2717
        self._entries_to_current_state(new_entries)
2532
2718
        self._parents = [rev_id for rev_id, tree in trees]
2533
2719
        self._ghosts = list(ghosts)
2534
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2535
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2720
        self._mark_modified(header_modified=True)
2536
2721
        self._id_index = id_index
2537
2722
 
2538
2723
    def _sort_entries(self, entry_list):
2542
2727
        try to keep everything in sorted blocks all the time, but sometimes
2543
2728
        it's easier to sort after the fact.
2544
2729
        """
2545
 
        def _key(entry):
 
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):
2546
2736
            # sort by: directory parts, file name, file id
2547
 
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
 
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)
2548
2744
        return sorted(entry_list, key=_key)
2549
2745
 
2550
2746
    def set_state_from_inventory(self, new_inv):
2675
2871
                        current_old[0][1].decode('utf8'))
2676
2872
                self._make_absent(current_old)
2677
2873
                current_old = advance(old_iterator)
2678
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2874
        self._mark_modified()
2679
2875
        self._id_index = None
2680
2876
        self._packed_stat_index = None
2681
2877
        if tracing:
2682
2878
            trace.mutter("set_state_from_inventory complete.")
2683
2879
 
 
2880
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
 
2881
        """Wipe the currently stored state and set it to something new.
 
2882
 
 
2883
        This is a hard-reset for the data we are working with.
 
2884
        """
 
2885
        # Technically, we really want a write lock, but until we write, we
 
2886
        # don't really need it.
 
2887
        self._requires_lock()
 
2888
        # root dir and root dir contents with no children. We have to have a
 
2889
        # root for set_state_from_inventory to work correctly.
 
2890
        empty_root = (('', '', inventory.ROOT_ID),
 
2891
                      [('d', '', 0, False, DirState.NULLSTAT)])
 
2892
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
 
2893
        self._set_data([], empty_tree_dirblocks)
 
2894
        self.set_state_from_inventory(working_inv)
 
2895
        self.set_parent_trees(parent_trees, parent_ghosts)
 
2896
 
2684
2897
    def _make_absent(self, current_old):
2685
2898
        """Mark current_old - an entry - as absent for tree 0.
2686
2899
 
2730
2943
            if update_tree_details[0][0] == 'a': # absent
2731
2944
                raise AssertionError('bad row %r' % (update_tree_details,))
2732
2945
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2733
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2946
        self._mark_modified()
2734
2947
        return last_reference
2735
2948
 
2736
2949
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2778
2991
                            # This entry has the same path (but a different id) as
2779
2992
                            # the new entry we're adding, and is present in ths
2780
2993
                            # tree.
2781
 
                            raise errors.InconsistentDelta(
 
2994
                            self._raise_invalid(
2782
2995
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2783
2996
                                "Attempt to add item at path already occupied by "
2784
2997
                                "id %r" % entry[0][2])
2905
3118
            if not present:
2906
3119
                self._dirblocks.insert(block_index, (subdir_key[0], []))
2907
3120
 
2908
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3121
        self._mark_modified()
2909
3122
 
2910
3123
    def _maybe_remove_row(self, block, index, id_index):
2911
3124
        """Remove index if it is absent or relocated across the row.
3137
3350
 
3138
3351
 
3139
3352
def py_update_entry(state, entry, abspath, stat_value,
3140
 
                 _stat_to_minikind=DirState._stat_to_minikind,
3141
 
                 _pack_stat=pack_stat):
 
3353
                 _stat_to_minikind=DirState._stat_to_minikind):
3142
3354
    """Update the entry based on what is actually on disk.
3143
3355
 
3144
3356
    This function only calculates the sha if it needs to - if the entry is
3157
3369
    except KeyError:
3158
3370
        # Unhandled kind
3159
3371
        return None
3160
 
    packed_stat = _pack_stat(stat_value)
 
3372
    packed_stat = pack_stat(stat_value)
3161
3373
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3162
3374
     saved_executable, saved_packed_stat) = entry[1][0]
3163
3375
 
3177
3389
    # If we have gotten this far, that means that we need to actually
3178
3390
    # process this entry.
3179
3391
    link_or_sha1 = None
 
3392
    worth_saving = True
3180
3393
    if minikind == 'f':
3181
3394
        executable = state._is_executable(stat_value.st_mode,
3182
3395
                                         saved_executable)
3198
3411
        else:
3199
3412
            entry[1][0] = ('f', '', stat_value.st_size,
3200
3413
                           executable, DirState.NULLSTAT)
 
3414
            worth_saving = False
3201
3415
    elif minikind == 'd':
3202
3416
        link_or_sha1 = None
3203
3417
        entry[1][0] = ('d', '', 0, False, packed_stat)
3209
3423
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3210
3424
            state._ensure_block(block_index, entry_index,
3211
3425
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
3426
        else:
 
3427
            worth_saving = False
3212
3428
    elif minikind == 'l':
 
3429
        if saved_minikind == 'l':
 
3430
            worth_saving = False
3213
3431
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3214
3432
        if state._cutoff_time is None:
3215
3433
            state._sha_cutoff_time()
3220
3438
        else:
3221
3439
            entry[1][0] = ('l', '', stat_value.st_size,
3222
3440
                           False, DirState.NULLSTAT)
3223
 
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3441
    if worth_saving:
 
3442
        state._mark_modified([entry])
3224
3443
    return link_or_sha1
3225
3444
 
3226
3445
 
3535
3754
            raise AssertionError("don't know how to compare "
3536
3755
                "source_minikind=%r, target_minikind=%r"
3537
3756
                % (source_minikind, target_minikind))
3538
 
            ## import pdb;pdb.set_trace()
3539
3757
        return None, None
3540
3758
 
3541
3759
    def __iter__(self):
4030
4248
        _bisect_path_left,
4031
4249
        _bisect_path_right,
4032
4250
        cmp_by_dirs,
 
4251
        pack_stat,
4033
4252
        ProcessEntryC as _process_entry,
4034
4253
        update_entry as update_entry,
4035
4254
        )
4041
4260
        _bisect_path_left,
4042
4261
        _bisect_path_right,
4043
4262
        cmp_by_dirs,
 
4263
        pack_stat,
4044
4264
        )
4045
4265
    # FIXME: It would be nice to be able to track moved lines so that the
4046
4266
    # corresponding python code can be moved to the _dirstate_helpers_py