~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: John Arbash Meinel
  • Date: 2013-05-23 10:04:17 UTC
  • mfrom: (6437.63.11 2.5)
  • mto: This revision was merged to the branch mainline in revision 6575.
  • Revision ID: john@arbash-meinel.com-20130523100417-i38zikta14q2xdyz
Merge lp:bzr/2.5 tip and move up the changelog items.

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
                self._raise_invalid(new_path, file_id,
 
1652
                    "Unable to find block for this record."
 
1653
                    " Was the parent added?")
 
1654
            block = self._dirblocks[block_index][1]
 
1655
            entry_index, present = self._find_entry_index(entry_key, block)
 
1656
            if real_add:
 
1657
                if old_path is not None:
 
1658
                    self._raise_invalid(new_path, file_id,
 
1659
                        'considered a real add but still had old_path at %s'
 
1660
                        % (old_path,))
 
1661
            if present:
 
1662
                entry = block[entry_index]
 
1663
                basis_kind = entry[1][1][0]
 
1664
                if basis_kind == 'a':
 
1665
                    entry[1][1] = new_details
 
1666
                elif basis_kind == 'r':
 
1667
                    raise NotImplementedError()
 
1668
                else:
 
1669
                    self._raise_invalid(new_path, file_id,
 
1670
                        "An entry was marked as a new add"
 
1671
                        " but the basis target already existed")
 
1672
            else:
 
1673
                # The exact key was not found in the block. However, we need to
 
1674
                # check if there is a key next to us that would have matched.
 
1675
                # We only need to check 2 locations, because there are only 2
 
1676
                # trees present.
 
1677
                for maybe_index in range(entry_index-1, entry_index+1):
 
1678
                    if maybe_index < 0 or maybe_index >= len(block):
 
1679
                        continue
 
1680
                    maybe_entry = block[maybe_index]
 
1681
                    if maybe_entry[0][:2] != (dirname, basename):
 
1682
                        # Just a random neighbor
 
1683
                        continue
 
1684
                    if maybe_entry[0][2] == file_id:
 
1685
                        raise AssertionError(
 
1686
                            '_find_entry_index didnt find a key match'
 
1687
                            ' but walking the data did, for %s'
 
1688
                            % (entry_key,))
 
1689
                    basis_kind = maybe_entry[1][1][0]
 
1690
                    if basis_kind not in 'ar':
 
1691
                        self._raise_invalid(new_path, file_id,
 
1692
                            "we have an add record for path, but the path"
 
1693
                            " is already present with another file_id %s"
 
1694
                            % (maybe_entry[0][2],))
 
1695
 
 
1696
                entry = (entry_key, [DirState.NULL_PARENT_DETAILS,
 
1697
                                     new_details])
 
1698
                block.insert(entry_index, entry)
 
1699
 
 
1700
            active_kind = entry[1][0][0]
 
1701
            if active_kind == 'a':
 
1702
                # The active record shows up as absent, this could be genuine,
 
1703
                # or it could be present at some other location. We need to
 
1704
                # verify.
 
1705
                id_index = self._get_id_index()
 
1706
                # The id_index may not be perfectly accurate for tree1, because
 
1707
                # we haven't been keeping it updated. However, it should be
 
1708
                # fine for tree0, and that gives us enough info for what we
 
1709
                # need
 
1710
                keys = id_index.get(file_id, ())
 
1711
                for key in keys:
 
1712
                    block_i, entry_i, d_present, f_present = \
 
1713
                        self._get_block_entry_index(key[0], key[1], 0)
 
1714
                    if not f_present:
 
1715
                        continue
 
1716
                    active_entry = self._dirblocks[block_i][1][entry_i]
 
1717
                    if (active_entry[0][2] != file_id):
 
1718
                        # Some other file is at this path, we don't need to
 
1719
                        # link it.
 
1720
                        continue
 
1721
                    real_active_kind = active_entry[1][0][0]
 
1722
                    if real_active_kind in 'ar':
 
1723
                        # We found a record, which was not *this* record,
 
1724
                        # which matches the file_id, but is not actually
 
1725
                        # present. Something seems *really* wrong.
 
1726
                        self._raise_invalid(new_path, file_id,
 
1727
                            "We found a tree0 entry that doesnt make sense")
 
1728
                    # Now, we've found a tree0 entry which matches the file_id
 
1729
                    # but is at a different location. So update them to be
 
1730
                    # rename records.
 
1731
                    active_dir, active_name = active_entry[0][:2]
 
1732
                    if active_dir:
 
1733
                        active_path = active_dir + '/' + active_name
 
1734
                    else:
 
1735
                        active_path = active_name
 
1736
                    active_entry[1][1] = st('r', new_path, 0, False, '')
 
1737
                    entry[1][0] = st('r', active_path, 0, False, '')
 
1738
            elif active_kind == 'r':
 
1739
                raise NotImplementedError()
 
1740
 
 
1741
            new_kind = new_details[0]
 
1742
            if new_kind == 'd':
 
1743
                self._ensure_block(block_index, entry_index, new_path)
1620
1744
 
1621
1745
    def _update_basis_apply_changes(self, changes):
1622
1746
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1627
1751
        absent = 'ar'
1628
1752
        for old_path, new_path, file_id, new_details in changes:
1629
1753
            # 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')
 
1754
            entry = self._get_entry(1, file_id, new_path)
 
1755
            if entry[0] is None or entry[1][1][0] in 'ar':
 
1756
                self._raise_invalid(new_path, file_id,
 
1757
                    'changed entry considered not present')
1640
1758
            entry[1][1] = new_details
1641
1759
 
1642
1760
    def _update_basis_apply_deletes(self, deletes):
1654
1772
        null = DirState.NULL_PARENT_DETAILS
1655
1773
        for old_path, new_path, file_id, _, real_delete in deletes:
1656
1774
            if real_delete != (new_path is None):
1657
 
                self._changes_aborted = True
1658
 
                raise AssertionError("bad delete delta")
 
1775
                self._raise_invalid(old_path, file_id, "bad delete delta")
1659
1776
            # the entry for this file_id must be in tree 1.
1660
1777
            dirname, basename = osutils.split(old_path)
1661
1778
            block_index, entry_index, dir_present, file_present = \
1662
1779
                self._get_block_entry_index(dirname, basename, 1)
1663
1780
            if not file_present:
1664
 
                self._changes_aborted = True
1665
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1781
                self._raise_invalid(old_path, file_id,
1666
1782
                    'basis tree does not contain removed entry')
1667
1783
            entry = self._dirblocks[block_index][1][entry_index]
 
1784
            # The state of the entry in the 'active' WT
 
1785
            active_kind = entry[1][0][0]
1668
1786
            if entry[0][2] != file_id:
1669
 
                self._changes_aborted = True
1670
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1787
                self._raise_invalid(old_path, file_id,
1671
1788
                    '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.')
 
1789
            dir_block = ()
 
1790
            old_kind = entry[1][1][0]
 
1791
            if active_kind in 'ar':
 
1792
                # The active tree doesn't have this file_id.
 
1793
                # The basis tree is changing this record. If this is a
 
1794
                # rename, then we don't want the record here at all
 
1795
                # anymore. If it is just an in-place change, we want the
 
1796
                # record here, but we'll add it if we need to. So we just
 
1797
                # delete it
 
1798
                if active_kind == 'r':
 
1799
                    active_path = entry[1][0][1]
 
1800
                    active_entry = self._get_entry(0, file_id, active_path)
 
1801
                    if active_entry[1][1][0] != 'r':
 
1802
                        self._raise_invalid(old_path, file_id,
 
1803
                            "Dirstate did not have matching rename entries")
 
1804
                    elif active_entry[1][0][0] in 'ar':
 
1805
                        self._raise_invalid(old_path, file_id,
 
1806
                            "Dirstate had a rename pointing at an inactive"
 
1807
                            " tree0")
 
1808
                    active_entry[1][1] = null
1678
1809
                del self._dirblocks[block_index][1][entry_index]
 
1810
                if old_kind == 'd':
 
1811
                    # This was a directory, and the active tree says it
 
1812
                    # doesn't exist, and now the basis tree says it doesn't
 
1813
                    # exist. Remove its dirblock if present
 
1814
                    (dir_block_index,
 
1815
                     present) = self._find_block_index_from_key(
 
1816
                        (old_path, '', ''))
 
1817
                    if present:
 
1818
                        dir_block = self._dirblocks[dir_block_index][1]
 
1819
                        if not dir_block:
 
1820
                            # This entry is empty, go ahead and just remove it
 
1821
                            del self._dirblocks[dir_block_index]
1679
1822
            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
 
1823
                # There is still an active record, so just mark this
 
1824
                # removed.
 
1825
                entry[1][1] = null
 
1826
                block_i, entry_i, d_present, f_present = \
 
1827
                    self._get_block_entry_index(old_path, '', 1)
 
1828
                if d_present:
 
1829
                    dir_block = self._dirblocks[block_i][1]
 
1830
            for child_entry in dir_block:
 
1831
                child_basis_kind = child_entry[1][1][0]
 
1832
                if child_basis_kind not in 'ar':
 
1833
                    self._raise_invalid(old_path, file_id,
 
1834
                        "The file id was deleted but its children were "
 
1835
                        "not deleted.")
1695
1836
 
1696
1837
    def _after_delta_check_parents(self, parents, index):
1697
1838
        """Check that parents required by the delta are all intact.
1706
1847
            # has the right file id.
1707
1848
            entry = self._get_entry(index, file_id, dirname_utf8)
1708
1849
            if entry[1] is None:
1709
 
                self._changes_aborted = True
1710
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1850
                self._raise_invalid(dirname_utf8.decode('utf8'),
1711
1851
                    file_id, "This parent is not present.")
1712
1852
            # Parents of things must be directories
1713
1853
            if entry[1][index][0] != 'd':
1714
 
                self._changes_aborted = True
1715
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1854
                self._raise_invalid(dirname_utf8.decode('utf8'),
1716
1855
                    file_id, "This parent is not a directory.")
1717
1856
 
1718
1857
    def _observed_sha1(self, entry, sha1, stat_value,
1719
 
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
 
1858
        _stat_to_minikind=_stat_to_minikind):
1720
1859
        """Note the sha1 of a file.
1721
1860
 
1722
1861
        :param entry: The entry the sha1 is for.
1728
1867
        except KeyError:
1729
1868
            # Unhandled kind
1730
1869
            return None
1731
 
        packed_stat = _pack_stat(stat_value)
1732
1870
        if minikind == 'f':
1733
1871
            if self._cutoff_time is None:
1734
1872
                self._sha_cutoff_time()
1735
1873
            if (stat_value.st_mtime < self._cutoff_time
1736
1874
                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
 
1875
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
 
1876
                               pack_stat(stat_value))
 
1877
                self._mark_modified([entry])
1740
1878
 
1741
1879
    def _sha_cutoff_time(self):
1742
1880
        """Return cutoff time.
1786
1924
            # paths are produced by UnicodeDirReader on purpose.
1787
1925
            abspath = abspath.encode(fs_encoding)
1788
1926
        target = os.readlink(abspath)
1789
 
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
 
1927
        if fs_encoding not in ('utf-8', 'ascii'):
1790
1928
            # Change encoding if needed
1791
1929
            target = target.decode(fs_encoding).encode('UTF-8')
1792
1930
        return target
1800
1938
        """Serialise the entire dirstate to a sequence of lines."""
1801
1939
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1802
1940
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1803
 
            # read whats on disk.
 
1941
            # read what's on disk.
1804
1942
            self._state_file.seek(0)
1805
1943
            return self._state_file.readlines()
1806
1944
        lines = []
1807
1945
        lines.append(self._get_parents_line(self.get_parent_ids()))
1808
1946
        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()))
 
1947
        lines.extend(self._get_entry_lines())
1811
1948
        return self._get_output_lines(lines)
1812
1949
 
1813
1950
    def _get_ghosts_line(self, ghost_ids):
1818
1955
        """Create a line for the state file for parents information."""
1819
1956
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1820
1957
 
 
1958
    def _get_entry_lines(self):
 
1959
        """Create lines for entries."""
 
1960
        return map(self._entry_to_line, self._iter_entries())
 
1961
 
1821
1962
    def _get_fields_to_entry(self):
1822
1963
        """Get a function which converts entry fields into a entry record.
1823
1964
 
1941
2082
            entry_index += 1
1942
2083
        return block_index, entry_index, True, False
1943
2084
 
1944
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
2085
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
 
2086
                   include_deleted=False):
1945
2087
        """Get the dirstate entry for path in tree tree_index.
1946
2088
 
1947
2089
        If either file_id or path is supplied, it is used as the key to lookup.
2089
2231
            executable = False
2090
2232
        else:
2091
2233
            raise Exception("can't pack %s" % inv_entry)
2092
 
        return (minikind, fingerprint, size, executable, tree_data)
 
2234
        return static_tuple.StaticTuple(minikind, fingerprint, size,
 
2235
                                        executable, tree_data)
2093
2236
 
2094
2237
    def _iter_child_entries(self, tree_index, path_utf8):
2095
2238
        """Iterate over all the entries that are children of path_utf.
2145
2288
 
2146
2289
    def _get_id_index(self):
2147
2290
        """Get an id index of self._dirblocks.
2148
 
        
 
2291
 
2149
2292
        This maps from file_id => [(directory, name, file_id)] entries where
2150
2293
        that file_id appears in one of the trees.
2151
2294
        """
2165
2308
        # such, we use a simple tuple, and do our own uniqueness checks. While
2166
2309
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2167
2310
        # cause quadratic failure.
2168
 
        # TODO: This should use StaticTuple
2169
2311
        file_id = entry_key[2]
2170
2312
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2171
2313
        if file_id not in id_index:
2211
2353
        """The number of parent entries in each record row."""
2212
2354
        return len(self._parents) - len(self._ghosts)
2213
2355
 
2214
 
    @staticmethod
2215
 
    def on_file(path, sha1_provider=None):
 
2356
    @classmethod
 
2357
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
2216
2358
        """Construct a DirState on the file at path "path".
2217
2359
 
2218
2360
        :param path: The path at which the dirstate file on disk should live.
2219
2361
        :param sha1_provider: an object meeting the SHA1Provider interface.
2220
2362
            If None, a DefaultSHA1Provider is used.
 
2363
        :param worth_saving_limit: when the exact number of hash changed
 
2364
            entries is known, only bother saving the dirstate if more than
 
2365
            this count of entries have changed. -1 means never save.
2221
2366
        :return: An unlocked DirState object, associated with the given path.
2222
2367
        """
2223
2368
        if sha1_provider is None:
2224
2369
            sha1_provider = DefaultSHA1Provider()
2225
 
        result = DirState(path, sha1_provider)
 
2370
        result = cls(path, sha1_provider,
 
2371
                     worth_saving_limit=worth_saving_limit)
2226
2372
        return result
2227
2373
 
2228
2374
    def _read_dirblocks_if_needed(self):
2286
2432
            raise errors.BzrError('missing num_entries line')
2287
2433
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2288
2434
 
2289
 
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
 
2435
    def sha1_from_stat(self, path, stat_result):
2290
2436
        """Find a sha1 given a stat lookup."""
2291
 
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
 
2437
        return self._get_packed_stat_index().get(pack_stat(stat_result), None)
2292
2438
 
2293
2439
    def _get_packed_stat_index(self):
2294
2440
        """Get a packed_stat index of self._dirblocks."""
2320
2466
            trace.mutter('Not saving DirState because '
2321
2467
                    '_changes_aborted is set.')
2322
2468
            return
2323
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2324
 
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
2469
        # TODO: Since we now distinguish IN_MEMORY_MODIFIED from
 
2470
        #       IN_MEMORY_HASH_MODIFIED, we should only fail quietly if we fail
 
2471
        #       to save an IN_MEMORY_HASH_MODIFIED, and fail *noisily* if we
 
2472
        #       fail to save IN_MEMORY_MODIFIED
 
2473
        if not self._worth_saving():
 
2474
            return
2325
2475
 
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.
 
2476
        grabbed_write_lock = False
 
2477
        if self._lock_state != 'w':
 
2478
            grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
 
2479
            # Switch over to the new lock, as the old one may be closed.
 
2480
            # TODO: jam 20070315 We should validate the disk file has
 
2481
            #       not changed contents, since temporary_write_lock may
 
2482
            #       not be an atomic operation.
 
2483
            self._lock_token = new_lock
 
2484
            self._state_file = new_lock.f
 
2485
            if not grabbed_write_lock:
 
2486
                # We couldn't grab a write lock, so we switch back to a read one
 
2487
                return
 
2488
        try:
 
2489
            lines = self.get_lines()
 
2490
            self._state_file.seek(0)
 
2491
            self._state_file.writelines(lines)
 
2492
            self._state_file.truncate()
 
2493
            self._state_file.flush()
 
2494
            self._maybe_fdatasync()
 
2495
            self._mark_unmodified()
 
2496
        finally:
 
2497
            if grabbed_write_lock:
 
2498
                self._lock_token = self._lock_token.restore_read_lock()
 
2499
                self._state_file = self._lock_token.f
2330
2500
                # 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.
 
2501
                #       not changed contents. Since restore_read_lock may
 
2502
                #       not be an atomic operation.                
 
2503
 
 
2504
    def _maybe_fdatasync(self):
 
2505
        """Flush to disk if possible and if not configured off."""
 
2506
        if self._config_stack.get('dirstate.fdatasync'):
 
2507
            osutils.fdatasync(self._state_file.fileno())
 
2508
 
 
2509
    def _worth_saving(self):
 
2510
        """Is it worth saving the dirstate or not?"""
 
2511
        if (self._header_state == DirState.IN_MEMORY_MODIFIED
 
2512
            or self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
2513
            return True
 
2514
        if self._dirblock_state == DirState.IN_MEMORY_HASH_MODIFIED:
 
2515
            if self._worth_saving_limit == -1:
 
2516
                # We never save hash changes when the limit is -1
 
2517
                return False
 
2518
            # If we're using smart saving and only a small number of
 
2519
            # entries have changed their hash, don't bother saving. John has
 
2520
            # suggested using a heuristic here based on the size of the
 
2521
            # changed files and/or tree. For now, we go with a configurable
 
2522
            # number of changes, keeping the calculation time
 
2523
            # as low overhead as possible. (This also keeps all existing
 
2524
            # tests passing as the default is 0, i.e. always save.)
 
2525
            if len(self._known_hash_changes) >= self._worth_saving_limit:
 
2526
                return True
 
2527
        return False
2352
2528
 
2353
2529
    def _set_data(self, parent_ids, dirblocks):
2354
2530
        """Set the full dirstate data in memory.
2363
2539
        """
2364
2540
        # our memory copy is now authoritative.
2365
2541
        self._dirblocks = dirblocks
2366
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2367
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2542
        self._mark_modified(header_modified=True)
2368
2543
        self._parents = list(parent_ids)
2369
2544
        self._id_index = None
2370
2545
        self._packed_stat_index = None
2390
2565
        self._make_absent(entry)
2391
2566
        self.update_minimal(('', '', new_id), 'd',
2392
2567
            path_utf8='', packed_stat=entry[1][0][4])
2393
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2568
        self._mark_modified()
2394
2569
 
2395
2570
    def set_parent_trees(self, trees, ghosts):
2396
2571
        """Set the parent trees for the dirstate.
2441
2616
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2442
2617
        # how many trees do we end up with
2443
2618
        parent_count = len(parent_trees)
 
2619
        st = static_tuple.StaticTuple
2444
2620
 
2445
2621
        # one: the current tree
2446
2622
        for entry in self._iter_entries():
2463
2639
            # the suffix is from tree_index+1:parent_count+1.
2464
2640
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2465
2641
            # now stitch in all the entries from this tree
2466
 
            for path, entry in tree.inventory.iter_entries_by_dir():
 
2642
            last_dirname = None
 
2643
            for path, entry in tree.iter_entries_by_dir():
2467
2644
                # here we process each trees details for each item in the tree.
2468
2645
                # we first update any existing entries for the id at other paths,
2469
2646
                # then we either create or update the entry for the id at the
2476
2653
                file_id = entry.file_id
2477
2654
                path_utf8 = path.encode('utf8')
2478
2655
                dirname, basename = osutils.split(path_utf8)
2479
 
                new_entry_key = (dirname, basename, file_id)
 
2656
                if dirname == last_dirname:
 
2657
                    # Try to re-use objects as much as possible
 
2658
                    dirname = last_dirname
 
2659
                else:
 
2660
                    last_dirname = dirname
 
2661
                new_entry_key = st(dirname, basename, file_id)
2480
2662
                # tree index consistency: All other paths for this id in this tree
2481
2663
                # index must point to the correct path.
2482
 
                for entry_key in id_index.get(file_id, ()):
 
2664
                entry_keys = id_index.get(file_id, ())
 
2665
                for entry_key in entry_keys:
2483
2666
                    # TODO:PROFILING: It might be faster to just update
2484
2667
                    # rather than checking if we need to, and then overwrite
2485
2668
                    # the one we are located at.
2488
2671
                        # other trees, so put absent pointers there
2489
2672
                        # This is the vertical axis in the matrix, all pointing
2490
2673
                        # 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, ())
 
2674
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
 
2675
                                                            False, '')
 
2676
                # by path consistency: Insert into an existing path record
 
2677
                # (trivial), or add a new one with relocation pointers for the
 
2678
                # other tree indexes.
2495
2679
                if new_entry_key in entry_keys:
2496
 
                    # there is already an entry where this data belongs, just insert it.
 
2680
                    # there is already an entry where this data belongs, just
 
2681
                    # insert it.
2497
2682
                    by_path[new_entry_key][tree_index] = \
2498
2683
                        self._inv_entry_to_details(entry)
2499
2684
                else:
2509
2694
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2510
2695
                        else:
2511
2696
                            # 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
2697
                            a_key = iter(entry_keys).next()
2516
2698
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2517
 
                                # its a pointer or missing statement, use it as is.
 
2699
                                # its a pointer or missing statement, use it as
 
2700
                                # is.
2518
2701
                                new_details.append(by_path[a_key][lookup_index])
2519
2702
                            else:
2520
2703
                                # we have the right key, make a pointer to it.
2521
2704
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2522
 
                                new_details.append(('r', real_path, 0, False, ''))
 
2705
                                new_details.append(st('r', real_path, 0, False,
 
2706
                                                      ''))
2523
2707
                    new_details.append(self._inv_entry_to_details(entry))
2524
2708
                    new_details.extend(new_location_suffix)
2525
2709
                    by_path[new_entry_key] = new_details
2531
2715
        self._entries_to_current_state(new_entries)
2532
2716
        self._parents = [rev_id for rev_id, tree in trees]
2533
2717
        self._ghosts = list(ghosts)
2534
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2535
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2718
        self._mark_modified(header_modified=True)
2536
2719
        self._id_index = id_index
2537
2720
 
2538
2721
    def _sort_entries(self, entry_list):
2542
2725
        try to keep everything in sorted blocks all the time, but sometimes
2543
2726
        it's easier to sort after the fact.
2544
2727
        """
2545
 
        def _key(entry):
 
2728
        # When sorting, we usually have 10x more entries than directories. (69k
 
2729
        # total entries, 4k directories). So cache the results of splitting.
 
2730
        # Saving time and objects. Also, use StaticTuple to avoid putting all
 
2731
        # of these object into python's garbage collector.
 
2732
        split_dirs = {}
 
2733
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
2546
2734
            # sort by: directory parts, file name, file id
2547
 
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
 
2735
            dirpath, fname, file_id = entry[0]
 
2736
            try:
 
2737
                split = _split_dirs[dirpath]
 
2738
            except KeyError:
 
2739
                split = _st.from_sequence(dirpath.split('/'))
 
2740
                _split_dirs[dirpath] = split
 
2741
            return _st(split, fname, file_id)
2548
2742
        return sorted(entry_list, key=_key)
2549
2743
 
2550
2744
    def set_state_from_inventory(self, new_inv):
2675
2869
                        current_old[0][1].decode('utf8'))
2676
2870
                self._make_absent(current_old)
2677
2871
                current_old = advance(old_iterator)
2678
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2872
        self._mark_modified()
2679
2873
        self._id_index = None
2680
2874
        self._packed_stat_index = None
2681
2875
        if tracing:
2682
2876
            trace.mutter("set_state_from_inventory complete.")
2683
2877
 
 
2878
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
 
2879
        """Wipe the currently stored state and set it to something new.
 
2880
 
 
2881
        This is a hard-reset for the data we are working with.
 
2882
        """
 
2883
        # Technically, we really want a write lock, but until we write, we
 
2884
        # don't really need it.
 
2885
        self._requires_lock()
 
2886
        # root dir and root dir contents with no children. We have to have a
 
2887
        # root for set_state_from_inventory to work correctly.
 
2888
        empty_root = (('', '', inventory.ROOT_ID),
 
2889
                      [('d', '', 0, False, DirState.NULLSTAT)])
 
2890
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
 
2891
        self._set_data([], empty_tree_dirblocks)
 
2892
        self.set_state_from_inventory(working_inv)
 
2893
        self.set_parent_trees(parent_trees, parent_ghosts)
 
2894
 
2684
2895
    def _make_absent(self, current_old):
2685
2896
        """Mark current_old - an entry - as absent for tree 0.
2686
2897
 
2730
2941
            if update_tree_details[0][0] == 'a': # absent
2731
2942
                raise AssertionError('bad row %r' % (update_tree_details,))
2732
2943
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2733
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2944
        self._mark_modified()
2734
2945
        return last_reference
2735
2946
 
2736
2947
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2778
2989
                            # This entry has the same path (but a different id) as
2779
2990
                            # the new entry we're adding, and is present in ths
2780
2991
                            # tree.
2781
 
                            raise errors.InconsistentDelta(
 
2992
                            self._raise_invalid(
2782
2993
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2783
2994
                                "Attempt to add item at path already occupied by "
2784
2995
                                "id %r" % entry[0][2])
2905
3116
            if not present:
2906
3117
                self._dirblocks.insert(block_index, (subdir_key[0], []))
2907
3118
 
2908
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3119
        self._mark_modified()
2909
3120
 
2910
3121
    def _maybe_remove_row(self, block, index, id_index):
2911
3122
        """Remove index if it is absent or relocated across the row.
3067
3278
        if self._id_index is not None:
3068
3279
            for file_id, entry_keys in self._id_index.iteritems():
3069
3280
                for entry_key in entry_keys:
 
3281
                    # Check that the entry in the map is pointing to the same
 
3282
                    # file_id
3070
3283
                    if entry_key[2] != file_id:
3071
3284
                        raise AssertionError(
3072
3285
                            'file_id %r did not match entry key %s'
3073
3286
                            % (file_id, entry_key))
 
3287
                    # And that from this entry key, we can look up the original
 
3288
                    # record
 
3289
                    block_index, present = self._find_block_index_from_key(entry_key)
 
3290
                    if not present:
 
3291
                        raise AssertionError('missing block for entry key: %r', entry_key)
 
3292
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
 
3293
                    if not present:
 
3294
                        raise AssertionError('missing entry for key: %r', entry_key)
3074
3295
                if len(entry_keys) != len(set(entry_keys)):
3075
3296
                    raise AssertionError(
3076
3297
                        'id_index contained non-unique data for %s'
3137
3358
 
3138
3359
 
3139
3360
def py_update_entry(state, entry, abspath, stat_value,
3140
 
                 _stat_to_minikind=DirState._stat_to_minikind,
3141
 
                 _pack_stat=pack_stat):
 
3361
                 _stat_to_minikind=DirState._stat_to_minikind):
3142
3362
    """Update the entry based on what is actually on disk.
3143
3363
 
3144
3364
    This function only calculates the sha if it needs to - if the entry is
3157
3377
    except KeyError:
3158
3378
        # Unhandled kind
3159
3379
        return None
3160
 
    packed_stat = _pack_stat(stat_value)
 
3380
    packed_stat = pack_stat(stat_value)
3161
3381
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3162
3382
     saved_executable, saved_packed_stat) = entry[1][0]
3163
3383
 
3177
3397
    # If we have gotten this far, that means that we need to actually
3178
3398
    # process this entry.
3179
3399
    link_or_sha1 = None
 
3400
    worth_saving = True
3180
3401
    if minikind == 'f':
3181
3402
        executable = state._is_executable(stat_value.st_mode,
3182
3403
                                         saved_executable)
3198
3419
        else:
3199
3420
            entry[1][0] = ('f', '', stat_value.st_size,
3200
3421
                           executable, DirState.NULLSTAT)
 
3422
            worth_saving = False
3201
3423
    elif minikind == 'd':
3202
3424
        link_or_sha1 = None
3203
3425
        entry[1][0] = ('d', '', 0, False, packed_stat)
3209
3431
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3210
3432
            state._ensure_block(block_index, entry_index,
3211
3433
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
3434
        else:
 
3435
            worth_saving = False
3212
3436
    elif minikind == 'l':
 
3437
        if saved_minikind == 'l':
 
3438
            worth_saving = False
3213
3439
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3214
3440
        if state._cutoff_time is None:
3215
3441
            state._sha_cutoff_time()
3220
3446
        else:
3221
3447
            entry[1][0] = ('l', '', stat_value.st_size,
3222
3448
                           False, DirState.NULLSTAT)
3223
 
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3449
    if worth_saving:
 
3450
        state._mark_modified([entry])
3224
3451
    return link_or_sha1
3225
3452
 
3226
3453
 
3535
3762
            raise AssertionError("don't know how to compare "
3536
3763
                "source_minikind=%r, target_minikind=%r"
3537
3764
                % (source_minikind, target_minikind))
3538
 
            ## import pdb;pdb.set_trace()
3539
3765
        return None, None
3540
3766
 
3541
3767
    def __iter__(self):
4030
4256
        _bisect_path_left,
4031
4257
        _bisect_path_right,
4032
4258
        cmp_by_dirs,
 
4259
        pack_stat,
4033
4260
        ProcessEntryC as _process_entry,
4034
4261
        update_entry as update_entry,
4035
4262
        )
4041
4268
        _bisect_path_left,
4042
4269
        _bisect_path_right,
4043
4270
        cmp_by_dirs,
 
4271
        pack_stat,
4044
4272
        )
4045
4273
    # FIXME: It would be nice to be able to track moved lines so that the
4046
4274
    # corresponding python code can be moved to the _dirstate_helpers_py