~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Vincent Ladeuil
  • Date: 2010-12-07 10:16:53 UTC
  • mto: (5575.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 5576.
  • Revision ID: v.ladeuil+lp@free.fr-20101207101653-20iiufih26buvmy3
Use assertLength as it provides a better ouput to debug tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2011 Canonical Ltd
 
1
# Copyright (C) 2006-2010 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
 
::
24
 
 
25
 
    MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
26
 
    NL = "\\n";
27
 
    NULL = "\\0";
28
 
    WHOLE_NUMBER = {digit}, digit;
29
 
    BOOLEAN = "y" | "n";
30
 
    REVISION_ID = a non-empty utf8 string;
31
 
    
32
 
    dirstate format = header line, full checksum, row count, parent details,
33
 
     ghost_details, entries;
34
 
    header line = "#bazaar dirstate flat format 3", NL;
35
 
    full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
36
 
    row count = "num_entries: ", WHOLE_NUMBER, NL;
37
 
    parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
38
 
    ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
39
 
    entries = {entry};
40
 
    entry = entry_key, current_entry_details, {parent_entry_details};
41
 
    entry_key = dirname,  basename, fileid;
42
 
    current_entry_details = common_entry_details, working_entry_details;
43
 
    parent_entry_details = common_entry_details, history_entry_details;
44
 
    common_entry_details = MINIKIND, fingerprint, size, executable
45
 
    working_entry_details = packed_stat
46
 
    history_entry_details = REVISION_ID;
47
 
    executable = BOOLEAN;
48
 
    size = WHOLE_NUMBER;
49
 
    fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
50
 
 
51
 
Given this definition, the following is useful to know::
52
 
 
53
 
    entry (aka row) - all the data for a given key.
54
 
    entry[0]: The key (dirname, basename, fileid)
55
 
    entry[0][0]: dirname
56
 
    entry[0][1]: basename
57
 
    entry[0][2]: fileid
58
 
    entry[1]: The tree(s) data for this path and id combination.
59
 
    entry[1][0]: The current tree
60
 
    entry[1][1]: The second tree
61
 
 
62
 
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate::
63
 
 
64
 
    entry[1][0][0]: minikind
65
 
    entry[1][0][1]: fingerprint
66
 
    entry[1][0][2]: size
67
 
    entry[1][0][3]: executable
68
 
    entry[1][0][4]: packed_stat
69
 
 
70
 
OR (for non tree-0)::
71
 
 
72
 
    entry[1][1][4]: revision_id
 
23
MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
 
24
NL = "\n";
 
25
NULL = "\0";
 
26
WHOLE_NUMBER = {digit}, digit;
 
27
BOOLEAN = "y" | "n";
 
28
REVISION_ID = a non-empty utf8 string;
 
29
 
 
30
dirstate format = header line, full checksum, row count, parent details,
 
31
 ghost_details, entries;
 
32
header line = "#bazaar dirstate flat format 3", NL;
 
33
full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
 
34
row count = "num_entries: ", WHOLE_NUMBER, NL;
 
35
parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
 
36
ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
 
37
entries = {entry};
 
38
entry = entry_key, current_entry_details, {parent_entry_details};
 
39
entry_key = dirname,  basename, fileid;
 
40
current_entry_details = common_entry_details, working_entry_details;
 
41
parent_entry_details = common_entry_details, history_entry_details;
 
42
common_entry_details = MINIKIND, fingerprint, size, executable
 
43
working_entry_details = packed_stat
 
44
history_entry_details = REVISION_ID;
 
45
executable = BOOLEAN;
 
46
size = WHOLE_NUMBER;
 
47
fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
 
48
 
 
49
Given this definition, the following is useful to know:
 
50
entry (aka row) - all the data for a given key.
 
51
entry[0]: The key (dirname, basename, fileid)
 
52
entry[0][0]: dirname
 
53
entry[0][1]: basename
 
54
entry[0][2]: fileid
 
55
entry[1]: The tree(s) data for this path and id combination.
 
56
entry[1][0]: The current tree
 
57
entry[1][1]: The second tree
 
58
 
 
59
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate:
 
60
entry[1][0][0]: minikind
 
61
entry[1][0][1]: fingerprint
 
62
entry[1][0][2]: size
 
63
entry[1][0][3]: executable
 
64
entry[1][0][4]: packed_stat
 
65
OR (for non tree-0)
 
66
entry[1][1][4]: revision_id
73
67
 
74
68
There may be multiple rows at the root, one per id present in the root, so the
75
 
in memory root row is now::
76
 
 
77
 
    self._dirblocks[0] -> ('', [entry ...]),
78
 
 
79
 
and the entries in there are::
80
 
 
81
 
    entries[0][0]: ''
82
 
    entries[0][1]: ''
83
 
    entries[0][2]: file_id
84
 
    entries[1][0]: The tree data for the current tree for this fileid at /
85
 
    etc.
86
 
 
87
 
Kinds::
88
 
 
89
 
    'r' is a relocated entry: This path is not present in this tree with this
90
 
        id, but the id can be found at another location. The fingerprint is
91
 
        used to point to the target location.
92
 
    'a' is an absent entry: In that tree the id is not present at this path.
93
 
    'd' is a directory entry: This path in this tree is a directory with the
94
 
        current file id. There is no fingerprint for directories.
95
 
    'f' is a file entry: As for directory, but it's a file. The fingerprint is
96
 
        the sha1 value of the file's canonical form, i.e. after any read
97
 
        filters have been applied to the convenience form stored in the working
98
 
        tree.
99
 
    'l' is a symlink entry: As for directory, but a symlink. The fingerprint is
100
 
        the link target.
101
 
    't' is a reference to a nested subtree; the fingerprint is the referenced
102
 
        revision.
 
69
in memory root row is now:
 
70
self._dirblocks[0] -> ('', [entry ...]),
 
71
and the entries in there are
 
72
entries[0][0]: ''
 
73
entries[0][1]: ''
 
74
entries[0][2]: file_id
 
75
entries[1][0]: The tree data for the current tree for this fileid at /
 
76
etc.
 
77
 
 
78
Kinds:
 
79
'r' is a relocated entry: This path is not present in this tree with this id,
 
80
    but the id can be found at another location. The fingerprint is used to
 
81
    point to the target location.
 
82
'a' is an absent entry: In that tree the id is not present at this path.
 
83
'd' is a directory entry: This path in this tree is a directory with the
 
84
    current file id. There is no fingerprint for directories.
 
85
'f' is a file entry: As for directory, but it's a file. The fingerprint is the
 
86
    sha1 value of the file's canonical form, i.e. after any read filters have
 
87
    been applied to the convenience form stored in the working tree.
 
88
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
 
89
    link target.
 
90
't' is a reference to a nested subtree; the fingerprint is the referenced
 
91
    revision.
103
92
 
104
93
Ordering:
105
94
 
106
 
The entries on disk and in memory are ordered according to the following keys::
 
95
The entries on disk and in memory are ordered according to the following keys:
107
96
 
108
97
    directory, as a list of components
109
98
    filename
110
99
    file-id
111
100
 
112
101
--- Format 1 had the following different definition: ---
113
 
 
114
 
::
115
 
 
116
 
    rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
117
 
        WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
118
 
        {PARENT ROW}
119
 
    PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
120
 
        basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
121
 
        SHA1
 
102
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
 
103
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
 
104
    {PARENT ROW}
 
105
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
 
106
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
 
107
    SHA1
122
108
 
123
109
PARENT ROW's are emitted for every parent that is not in the ghosts details
124
110
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
149
135
----
150
136
 
151
137
Design priorities:
152
 
 1. Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
153
 
 2. fall back current object model as needed.
154
 
 3. scale usably to the largest trees known today - say 50K entries. (mozilla
 
138
 1) Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
 
139
 2) fall back current object model as needed.
 
140
 3) scale usably to the largest trees known today - say 50K entries. (mozilla
155
141
    is an example of this)
156
142
 
157
143
 
158
144
Locking:
159
 
 
160
145
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
161
146
 been modified, but will require that we flush/ignore cached stat-hit data
162
147
 because we won't want to restat all files on disk just because a lock was
163
148
 acquired, yet we cannot trust the data after the previous lock was released.
164
149
 
165
 
Memory representation::
166
 
 
 
150
Memory representation:
167
151
 vector of all directories, and vector of the childen ?
168
152
   i.e.
169
153
     root_entrie = (direntry for root, [parent_direntries_for_root]),
183
167
    - What's the risk of error here? Once we have the base format being processed
184
168
      we should have a net win regardless of optimality. So we are going to
185
169
      go with what seems reasonable.
186
 
 
187
170
open questions:
188
171
 
189
172
Maybe we should do a test profile of the core structure - 10K simulated
218
201
 
219
202
"""
220
203
 
221
 
from __future__ import absolute_import
222
 
 
223
204
import bisect
 
205
import binascii
224
206
import errno
225
207
import operator
226
208
import os
227
209
from stat import S_IEXEC
228
210
import stat
 
211
import struct
229
212
import sys
230
213
import time
231
214
import zlib
232
215
 
233
216
from bzrlib import (
234
217
    cache_utf8,
235
 
    config,
236
218
    debug,
237
219
    errors,
238
220
    inventory,
240
222
    osutils,
241
223
    static_tuple,
242
224
    trace,
243
 
    urlutils,
244
225
    )
245
226
 
246
227
 
251
232
ERROR_DIRECTORY = 267
252
233
 
253
234
 
 
235
if not getattr(struct, '_compile', None):
 
236
    # Cannot pre-compile the dirstate pack_stat
 
237
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
 
238
        """Convert stat values into a packed representation."""
 
239
        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),
 
240
            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,
 
241
            st.st_mode))[:-1]
 
242
else:
 
243
    # compile the struct compiler we need, so as to only do it once
 
244
    from _struct import Struct
 
245
    _compiled_pack = Struct('>LLLLLL').pack
 
246
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):
 
247
        """Convert stat values into a packed representation."""
 
248
        # jam 20060614 it isn't really worth removing more entries if we
 
249
        # are going to leave it in packed form.
 
250
        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
 
251
        # With all entries, filesize is 5.9M and read time is maybe 280ms
 
252
        # well within the noise margin
 
253
 
 
254
        # base64 encoding always adds a final newline, so strip it off
 
255
        # The current version
 
256
        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),
 
257
            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
258
        # This is 0.060s / 1.520s faster by not encoding as much information
 
259
        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
 
260
        # This is not strictly faster than _encode(_pack())[:-1]
 
261
        # return '%X.%X.%X.%X.%X.%X' % (
 
262
        #      st.st_size, int(st.st_mtime), int(st.st_ctime),
 
263
        #      st.st_dev, st.st_ino, st.st_mode)
 
264
        # Similar to the _encode(_pack('>LL'))
 
265
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
 
266
 
 
267
 
254
268
class SHA1Provider(object):
255
269
    """An interface for getting sha1s of a file."""
256
270
 
341
355
    NOT_IN_MEMORY = 0
342
356
    IN_MEMORY_UNMODIFIED = 1
343
357
    IN_MEMORY_MODIFIED = 2
344
 
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
345
358
 
346
359
    # A pack_stat (the x's) that is just noise and will never match the output
347
360
    # of base64 encode.
348
361
    NULLSTAT = 'x' * 32
349
 
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
 
362
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
350
363
 
351
364
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
352
365
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
353
366
 
354
 
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
 
367
    def __init__(self, path, sha1_provider):
355
368
        """Create a  DirState object.
356
369
 
357
370
        :param path: The path at which the dirstate file on disk should live.
358
371
        :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.
363
372
        """
364
373
        # _header_state and _dirblock_state represent the current state
365
374
        # of the dirstate metadata and the per-row data respectiely.
402
411
        # during commit.
403
412
        self._last_block_index = None
404
413
        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))
411
414
 
412
415
    def __repr__(self):
413
416
        return "%s(%r)" % \
414
417
            (self.__class__.__name__, self._filename)
415
418
 
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
 
 
447
419
    def add(self, path, file_id, kind, stat, fingerprint):
448
420
        """Add a path to be tracked.
449
421
 
575
547
        if kind == 'directory':
576
548
           # insert a new dirblock
577
549
           self._ensure_block(block_index, entry_index, utf8path)
578
 
        self._mark_modified()
 
550
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
579
551
        if self._id_index:
580
552
            self._add_to_id_index(self._id_index, entry_key)
581
553
 
1047
1019
 
1048
1020
        self._ghosts = []
1049
1021
        self._parents = [parents[0]]
1050
 
        self._mark_modified(header_modified=True)
 
1022
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1023
        self._header_state = DirState.IN_MEMORY_MODIFIED
1051
1024
 
1052
1025
    def _empty_parent_info(self):
1053
1026
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1182
1155
    def _fields_per_entry(self):
1183
1156
        """How many null separated fields should be in each entry row.
1184
1157
 
1185
 
        Each line now has an extra '\\n' field which is not used
 
1158
        Each line now has an extra '\n' field which is not used
1186
1159
        so we just skip over it
1187
 
 
1188
 
        entry size::
 
1160
        entry size:
1189
1161
            3 fields for the key
1190
1162
            + number of fields per tree_data (5) * tree count
1191
1163
            + newline
1292
1264
                    parent_trees.append((parent_id, parent_tree))
1293
1265
                    parent_tree.lock_read()
1294
1266
                result.set_parent_trees(parent_trees, [])
1295
 
                result.set_state_from_inventory(tree.root_inventory)
 
1267
                result.set_state_from_inventory(tree.inventory)
1296
1268
            finally:
1297
1269
                for revid, parent_tree in parent_trees:
1298
1270
                    parent_tree.unlock()
1304
1276
            raise
1305
1277
        return result
1306
1278
 
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
 
 
1315
1279
    def update_by_delta(self, delta):
1316
1280
        """Apply an inventory delta to the dirstate for tree 0
1317
1281
 
1335
1299
        new_ids = set()
1336
1300
        # This loop transforms the delta to single atomic operations that can
1337
1301
        # be executed and validated.
1338
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1339
 
        for old_path, new_path, file_id, inv_entry in delta:
 
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):
1340
1309
            if (file_id in insertions) or (file_id in removals):
1341
 
                self._raise_invalid(old_path or new_path, file_id,
 
1310
                raise errors.InconsistentDelta(old_path or new_path, file_id,
1342
1311
                    "repeated file_id")
1343
1312
            if old_path is not None:
1344
1313
                old_path = old_path.encode('utf-8')
1347
1316
                new_ids.add(file_id)
1348
1317
            if new_path is not None:
1349
1318
                if inv_entry is None:
1350
 
                    self._raise_invalid(new_path, file_id,
 
1319
                    raise errors.InconsistentDelta(new_path, file_id,
1351
1320
                        "new_path with no entry")
1352
1321
                new_path = new_path.encode('utf-8')
1353
1322
                dirname_utf8, basename = osutils.split(new_path)
1394
1363
            # _get_entry raises BzrError when a request is inconsistent; we
1395
1364
            # want such errors to be shown as InconsistentDelta - and that 
1396
1365
            # fits the behaviour we trigger.
1397
 
            raise errors.InconsistentDeltaDelta(delta,
1398
 
                "error from _get_entry. %s" % (e,))
 
1366
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1399
1367
 
1400
1368
    def _apply_removals(self, removals):
1401
1369
        for file_id, path in sorted(removals, reverse=True,
1406
1374
            try:
1407
1375
                entry = self._dirblocks[block_i][1][entry_i]
1408
1376
            except IndexError:
1409
 
                self._raise_invalid(path, file_id,
 
1377
                self._changes_aborted = True
 
1378
                raise errors.InconsistentDelta(path, file_id,
1410
1379
                    "Wrong path for old path.")
1411
1380
            if not f_present or entry[1][0][0] in 'ar':
1412
 
                self._raise_invalid(path, file_id,
 
1381
                self._changes_aborted = True
 
1382
                raise errors.InconsistentDelta(path, file_id,
1413
1383
                    "Wrong path for old path.")
1414
1384
            if file_id != entry[0][2]:
1415
 
                self._raise_invalid(path, file_id,
 
1385
                self._changes_aborted = True
 
1386
                raise errors.InconsistentDelta(path, file_id,
1416
1387
                    "Attempt to remove path has wrong id - found %r."
1417
1388
                    % entry[0][2])
1418
1389
            self._make_absent(entry)
1428
1399
                # be due to it being in a parent tree, or a corrupt delta.
1429
1400
                for child_entry in self._dirblocks[block_i][1]:
1430
1401
                    if child_entry[1][0][0] not in ('r', 'a'):
1431
 
                        self._raise_invalid(path, entry[0][2],
 
1402
                        self._changes_aborted = True
 
1403
                        raise errors.InconsistentDelta(path, entry[0][2],
1432
1404
                            "The file id was deleted but its children were "
1433
1405
                            "not deleted.")
1434
1406
 
1438
1410
                self.update_minimal(key, minikind, executable, fingerprint,
1439
1411
                                    path_utf8=path_utf8)
1440
1412
        except errors.NotVersionedError:
1441
 
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
 
1413
            self._changes_aborted = True
 
1414
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
1442
1415
                "Missing parent")
1443
1416
 
1444
1417
    def update_basis_by_delta(self, delta, new_revid):
1452
1425
        Note that an exception during the operation of this method will leave
1453
1426
        the dirstate in a corrupt state where it should not be saved.
1454
1427
 
 
1428
        Finally, we expect all changes to be synchronising the basis tree with
 
1429
        the working tree.
 
1430
 
1455
1431
        :param new_revid: The new revision id for the trees parent.
1456
1432
        :param delta: An inventory delta (see apply_inventory_delta) describing
1457
1433
            the changes from the current left most parent revision to new_revid.
1469
1445
 
1470
1446
        self._parents[0] = new_revid
1471
1447
 
1472
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1448
        delta = sorted(delta, reverse=True)
1473
1449
        adds = []
1474
1450
        changes = []
1475
1451
        deletes = []
1496
1472
        new_ids = set()
1497
1473
        for old_path, new_path, file_id, inv_entry in delta:
1498
1474
            if inv_entry is not None and file_id != inv_entry.file_id:
1499
 
                self._raise_invalid(new_path, file_id,
 
1475
                raise errors.InconsistentDelta(new_path, file_id,
1500
1476
                    "mismatched entry file_id %r" % inv_entry)
1501
 
            if new_path is None:
1502
 
                new_path_utf8 = None
1503
 
            else:
 
1477
            if new_path is not None:
1504
1478
                if inv_entry is None:
1505
 
                    self._raise_invalid(new_path, file_id,
 
1479
                    raise errors.InconsistentDelta(new_path, file_id,
1506
1480
                        "new_path with no entry")
1507
1481
                new_path_utf8 = encode(new_path)
1508
1482
                # note the parent for validation
1510
1484
                if basename_utf8:
1511
1485
                    parents.add((dirname_utf8, inv_entry.parent_id))
1512
1486
            if old_path is None:
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,
 
1487
                adds.append((None, encode(new_path), file_id,
1518
1488
                    inv_to_entry(inv_entry), True))
1519
1489
                new_ids.add(file_id)
1520
1490
            elif new_path is None:
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:
 
1491
                deletes.append((encode(old_path), None, file_id, None, True))
 
1492
            elif (old_path, new_path) != root_only:
1534
1493
                # Renames:
1535
1494
                # Because renames must preserve their children we must have
1536
1495
                # processed all relocations and removes before hand. The sort
1546
1505
                self._update_basis_apply_deletes(deletes)
1547
1506
                deletes = []
1548
1507
                # Split into an add/delete pair recursively.
1549
 
                adds.append((old_path_utf8, new_path_utf8, file_id,
1550
 
                             inv_to_entry(inv_entry), False))
 
1508
                adds.append((None, new_path_utf8, file_id,
 
1509
                    inv_to_entry(inv_entry), False))
1551
1510
                # Expunge deletes that we've seen so that deleted/renamed
1552
1511
                # children of a rename directory are handled correctly.
1553
 
                new_deletes = reversed(list(
1554
 
                    self._iter_child_entries(1, old_path_utf8)))
 
1512
                new_deletes = reversed(list(self._iter_child_entries(1,
 
1513
                    encode(old_path))))
1555
1514
                # Remove the current contents of the tree at orig_path, and
1556
1515
                # reinsert at the correct new path.
1557
1516
                for entry in new_deletes:
1558
 
                    child_dirname, child_basename, child_file_id = entry[0]
1559
 
                    if child_dirname:
1560
 
                        source_path = child_dirname + '/' + child_basename
 
1517
                    if entry[0][0]:
 
1518
                        source_path = entry[0][0] + '/' + entry[0][1]
1561
1519
                    else:
1562
 
                        source_path = child_basename
 
1520
                        source_path = entry[0][1]
1563
1521
                    if new_path_utf8:
1564
 
                        target_path = \
1565
 
                            new_path_utf8 + source_path[len(old_path_utf8):]
 
1522
                        target_path = new_path_utf8 + source_path[len(old_path):]
1566
1523
                    else:
1567
 
                        if old_path_utf8 == '':
 
1524
                        if old_path == '':
1568
1525
                            raise AssertionError("cannot rename directory to"
1569
 
                                                 " itself")
1570
 
                        target_path = source_path[len(old_path_utf8) + 1:]
 
1526
                                " itself")
 
1527
                        target_path = source_path[len(old_path) + 1:]
1571
1528
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1572
1529
                    deletes.append(
1573
1530
                        (source_path, target_path, entry[0][2], None, False))
1574
1531
                deletes.append(
1575
 
                    (old_path_utf8, new_path_utf8, file_id, None, False))
1576
 
 
 
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)))
1577
1538
        self._check_delta_ids_absent(new_ids, delta, 1)
1578
1539
        try:
1579
1540
            # Finish expunging deletes/first half of renames.
1589
1550
            if 'integrity error' not in str(e):
1590
1551
                raise
1591
1552
            # _get_entry raises BzrError when a request is inconsistent; we
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,))
 
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.")
1596
1558
 
1597
 
        self._mark_modified(header_modified=True)
 
1559
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1560
        self._header_state = DirState.IN_MEMORY_MODIFIED
1598
1561
        self._id_index = None
1599
1562
        return
1600
1563
 
1614
1577
                if entry[0][2] != file_id:
1615
1578
                    # Different file_id, so not what we want.
1616
1579
                    continue
1617
 
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
 
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,
1618
1584
                    "This file_id is new in the delta but already present in "
1619
1585
                    "the target")
1620
1586
 
1621
 
    def _raise_invalid(self, path, file_id, reason):
1622
 
        self._changes_aborted = True
1623
 
        raise errors.InconsistentDelta(path, file_id, reason)
1624
 
 
1625
1587
    def _update_basis_apply_adds(self, adds):
1626
1588
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1627
1589
 
1635
1597
        """
1636
1598
        # Adds are accumulated partly from renames, so can be in any input
1637
1599
        # order - sort it.
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])
 
1600
        adds.sort()
1642
1601
        # adds is now in lexographic order, which places all parents before
1643
1602
        # their children, so we can process it linearly.
1644
1603
        absent = 'ar'
1645
 
        st = static_tuple.StaticTuple
1646
1604
        for old_path, new_path, file_id, new_details, real_add in adds:
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)
 
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
1744
1620
 
1745
1621
    def _update_basis_apply_changes(self, changes):
1746
1622
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1751
1627
        absent = 'ar'
1752
1628
        for old_path, new_path, file_id, new_details in changes:
1753
1629
            # the entry for this file_id must be in tree 0.
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')
 
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')
1758
1640
            entry[1][1] = new_details
1759
1641
 
1760
1642
    def _update_basis_apply_deletes(self, deletes):
1772
1654
        null = DirState.NULL_PARENT_DETAILS
1773
1655
        for old_path, new_path, file_id, _, real_delete in deletes:
1774
1656
            if real_delete != (new_path is None):
1775
 
                self._raise_invalid(old_path, file_id, "bad delete delta")
 
1657
                self._changes_aborted = True
 
1658
                raise AssertionError("bad delete delta")
1776
1659
            # the entry for this file_id must be in tree 1.
1777
1660
            dirname, basename = osutils.split(old_path)
1778
1661
            block_index, entry_index, dir_present, file_present = \
1779
1662
                self._get_block_entry_index(dirname, basename, 1)
1780
1663
            if not file_present:
1781
 
                self._raise_invalid(old_path, file_id,
 
1664
                self._changes_aborted = True
 
1665
                raise errors.InconsistentDelta(old_path, file_id,
1782
1666
                    'basis tree does not contain removed entry')
1783
1667
            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]
1786
1668
            if entry[0][2] != file_id:
1787
 
                self._raise_invalid(old_path, file_id,
 
1669
                self._changes_aborted = True
 
1670
                raise errors.InconsistentDelta(old_path, file_id,
1788
1671
                    'mismatched file_id in tree 1')
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
 
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.')
1809
1678
                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]
1822
1679
            else:
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.")
 
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
1836
1695
 
1837
1696
    def _after_delta_check_parents(self, parents, index):
1838
1697
        """Check that parents required by the delta are all intact.
1847
1706
            # has the right file id.
1848
1707
            entry = self._get_entry(index, file_id, dirname_utf8)
1849
1708
            if entry[1] is None:
1850
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1709
                self._changes_aborted = True
 
1710
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1851
1711
                    file_id, "This parent is not present.")
1852
1712
            # Parents of things must be directories
1853
1713
            if entry[1][index][0] != 'd':
1854
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1714
                self._changes_aborted = True
 
1715
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1855
1716
                    file_id, "This parent is not a directory.")
1856
1717
 
1857
1718
    def _observed_sha1(self, entry, sha1, stat_value,
1858
 
        _stat_to_minikind=_stat_to_minikind):
 
1719
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
1859
1720
        """Note the sha1 of a file.
1860
1721
 
1861
1722
        :param entry: The entry the sha1 is for.
1867
1728
        except KeyError:
1868
1729
            # Unhandled kind
1869
1730
            return None
 
1731
        packed_stat = _pack_stat(stat_value)
1870
1732
        if minikind == 'f':
1871
1733
            if self._cutoff_time is None:
1872
1734
                self._sha_cutoff_time()
1873
1735
            if (stat_value.st_mtime < self._cutoff_time
1874
1736
                and stat_value.st_ctime < self._cutoff_time):
1875
 
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
1876
 
                               pack_stat(stat_value))
1877
 
                self._mark_modified([entry])
 
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
1878
1740
 
1879
1741
    def _sha_cutoff_time(self):
1880
1742
        """Return cutoff time.
1924
1786
            # paths are produced by UnicodeDirReader on purpose.
1925
1787
            abspath = abspath.encode(fs_encoding)
1926
1788
        target = os.readlink(abspath)
1927
 
        if fs_encoding not in ('utf-8', 'ascii'):
 
1789
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
1928
1790
            # Change encoding if needed
1929
1791
            target = target.decode(fs_encoding).encode('UTF-8')
1930
1792
        return target
1938
1800
        """Serialise the entire dirstate to a sequence of lines."""
1939
1801
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1940
1802
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1941
 
            # read what's on disk.
 
1803
            # read whats on disk.
1942
1804
            self._state_file.seek(0)
1943
1805
            return self._state_file.readlines()
1944
1806
        lines = []
1945
1807
        lines.append(self._get_parents_line(self.get_parent_ids()))
1946
1808
        lines.append(self._get_ghosts_line(self._ghosts))
1947
 
        lines.extend(self._get_entry_lines())
 
1809
        # append the root line which is special cased
 
1810
        lines.extend(map(self._entry_to_line, self._iter_entries()))
1948
1811
        return self._get_output_lines(lines)
1949
1812
 
1950
1813
    def _get_ghosts_line(self, ghost_ids):
1955
1818
        """Create a line for the state file for parents information."""
1956
1819
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1957
1820
 
1958
 
    def _get_entry_lines(self):
1959
 
        """Create lines for entries."""
1960
 
        return map(self._entry_to_line, self._iter_entries())
1961
 
 
1962
1821
    def _get_fields_to_entry(self):
1963
1822
        """Get a function which converts entry fields into a entry record.
1964
1823
 
2082
1941
            entry_index += 1
2083
1942
        return block_index, entry_index, True, False
2084
1943
 
2085
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
2086
 
                   include_deleted=False):
 
1944
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
2087
1945
        """Get the dirstate entry for path in tree tree_index.
2088
1946
 
2089
1947
        If either file_id or path is supplied, it is used as the key to lookup.
2231
2089
            executable = False
2232
2090
        else:
2233
2091
            raise Exception("can't pack %s" % inv_entry)
2234
 
        return static_tuple.StaticTuple(minikind, fingerprint, size,
2235
 
                                        executable, tree_data)
 
2092
        return (minikind, fingerprint, size, executable, tree_data)
2236
2093
 
2237
2094
    def _iter_child_entries(self, tree_index, path_utf8):
2238
2095
        """Iterate over all the entries that are children of path_utf.
2288
2145
 
2289
2146
    def _get_id_index(self):
2290
2147
        """Get an id index of self._dirblocks.
2291
 
 
 
2148
        
2292
2149
        This maps from file_id => [(directory, name, file_id)] entries where
2293
2150
        that file_id appears in one of the trees.
2294
2151
        """
2308
2165
        # such, we use a simple tuple, and do our own uniqueness checks. While
2309
2166
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2310
2167
        # cause quadratic failure.
 
2168
        # TODO: This should use StaticTuple
2311
2169
        file_id = entry_key[2]
2312
2170
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2313
2171
        if file_id not in id_index:
2353
2211
        """The number of parent entries in each record row."""
2354
2212
        return len(self._parents) - len(self._ghosts)
2355
2213
 
2356
 
    @classmethod
2357
 
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
 
2214
    @staticmethod
 
2215
    def on_file(path, sha1_provider=None):
2358
2216
        """Construct a DirState on the file at path "path".
2359
2217
 
2360
2218
        :param path: The path at which the dirstate file on disk should live.
2361
2219
        :param sha1_provider: an object meeting the SHA1Provider interface.
2362
2220
            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.
2366
2221
        :return: An unlocked DirState object, associated with the given path.
2367
2222
        """
2368
2223
        if sha1_provider is None:
2369
2224
            sha1_provider = DefaultSHA1Provider()
2370
 
        result = cls(path, sha1_provider,
2371
 
                     worth_saving_limit=worth_saving_limit)
 
2225
        result = DirState(path, sha1_provider)
2372
2226
        return result
2373
2227
 
2374
2228
    def _read_dirblocks_if_needed(self):
2432
2286
            raise errors.BzrError('missing num_entries line')
2433
2287
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2434
2288
 
2435
 
    def sha1_from_stat(self, path, stat_result):
 
2289
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
2436
2290
        """Find a sha1 given a stat lookup."""
2437
 
        return self._get_packed_stat_index().get(pack_stat(stat_result), None)
 
2291
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
2438
2292
 
2439
2293
    def _get_packed_stat_index(self):
2440
2294
        """Get a packed_stat index of self._dirblocks."""
2466
2320
            trace.mutter('Not saving DirState because '
2467
2321
                    '_changes_aborted is set.')
2468
2322
            return
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
 
2323
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
 
2324
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2475
2325
 
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
 
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.
2500
2330
                # TODO: jam 20070315 We should validate the disk file has
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
 
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.
2528
2352
 
2529
2353
    def _set_data(self, parent_ids, dirblocks):
2530
2354
        """Set the full dirstate data in memory.
2539
2363
        """
2540
2364
        # our memory copy is now authoritative.
2541
2365
        self._dirblocks = dirblocks
2542
 
        self._mark_modified(header_modified=True)
 
2366
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2367
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2543
2368
        self._parents = list(parent_ids)
2544
2369
        self._id_index = None
2545
2370
        self._packed_stat_index = None
2565
2390
        self._make_absent(entry)
2566
2391
        self.update_minimal(('', '', new_id), 'd',
2567
2392
            path_utf8='', packed_stat=entry[1][0][4])
2568
 
        self._mark_modified()
2569
 
        # XXX: This was added by Ian, we need to make sure there
2570
 
        #      are tests for it, because it isn't in bzr.dev TRUNK
2571
 
        #      It looks like the only place it is called is in setting the root
2572
 
        #      id of the tree. So probably we never had an _id_index when we
2573
 
        #      don't even have a root yet.
2574
 
        if self._id_index is not None:
2575
 
            self._add_to_id_index(self._id_index, entry[0])
 
2393
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2576
2394
 
2577
2395
    def set_parent_trees(self, trees, ghosts):
2578
2396
        """Set the parent trees for the dirstate.
2623
2441
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2624
2442
        # how many trees do we end up with
2625
2443
        parent_count = len(parent_trees)
2626
 
        st = static_tuple.StaticTuple
2627
2444
 
2628
2445
        # one: the current tree
2629
2446
        for entry in self._iter_entries():
2646
2463
            # the suffix is from tree_index+1:parent_count+1.
2647
2464
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2648
2465
            # now stitch in all the entries from this tree
2649
 
            last_dirname = None
2650
 
            for path, entry in tree.iter_entries_by_dir():
 
2466
            for path, entry in tree.inventory.iter_entries_by_dir():
2651
2467
                # here we process each trees details for each item in the tree.
2652
2468
                # we first update any existing entries for the id at other paths,
2653
2469
                # then we either create or update the entry for the id at the
2660
2476
                file_id = entry.file_id
2661
2477
                path_utf8 = path.encode('utf8')
2662
2478
                dirname, basename = osutils.split(path_utf8)
2663
 
                if dirname == last_dirname:
2664
 
                    # Try to re-use objects as much as possible
2665
 
                    dirname = last_dirname
2666
 
                else:
2667
 
                    last_dirname = dirname
2668
 
                new_entry_key = st(dirname, basename, file_id)
 
2479
                new_entry_key = (dirname, basename, file_id)
2669
2480
                # tree index consistency: All other paths for this id in this tree
2670
2481
                # index must point to the correct path.
2671
 
                entry_keys = id_index.get(file_id, ())
2672
 
                for entry_key in entry_keys:
 
2482
                for entry_key in id_index.get(file_id, ()):
2673
2483
                    # TODO:PROFILING: It might be faster to just update
2674
2484
                    # rather than checking if we need to, and then overwrite
2675
2485
                    # the one we are located at.
2678
2488
                        # other trees, so put absent pointers there
2679
2489
                        # This is the vertical axis in the matrix, all pointing
2680
2490
                        # to the real path.
2681
 
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
2682
 
                                                            False, '')
2683
 
                # by path consistency: Insert into an existing path record
2684
 
                # (trivial), or add a new one with relocation pointers for the
2685
 
                # other tree indexes.
 
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, ())
2686
2495
                if new_entry_key in entry_keys:
2687
 
                    # there is already an entry where this data belongs, just
2688
 
                    # insert it.
 
2496
                    # there is already an entry where this data belongs, just insert it.
2689
2497
                    by_path[new_entry_key][tree_index] = \
2690
2498
                        self._inv_entry_to_details(entry)
2691
2499
                else:
2701
2509
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2702
2510
                        else:
2703
2511
                            # 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.
2704
2515
                            a_key = iter(entry_keys).next()
2705
2516
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2706
 
                                # its a pointer or missing statement, use it as
2707
 
                                # is.
 
2517
                                # its a pointer or missing statement, use it as is.
2708
2518
                                new_details.append(by_path[a_key][lookup_index])
2709
2519
                            else:
2710
2520
                                # we have the right key, make a pointer to it.
2711
2521
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2712
 
                                new_details.append(st('r', real_path, 0, False,
2713
 
                                                      ''))
 
2522
                                new_details.append(('r', real_path, 0, False, ''))
2714
2523
                    new_details.append(self._inv_entry_to_details(entry))
2715
2524
                    new_details.extend(new_location_suffix)
2716
2525
                    by_path[new_entry_key] = new_details
2722
2531
        self._entries_to_current_state(new_entries)
2723
2532
        self._parents = [rev_id for rev_id, tree in trees]
2724
2533
        self._ghosts = list(ghosts)
2725
 
        self._mark_modified(header_modified=True)
 
2534
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2535
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2726
2536
        self._id_index = id_index
2727
2537
 
2728
2538
    def _sort_entries(self, entry_list):
2732
2542
        try to keep everything in sorted blocks all the time, but sometimes
2733
2543
        it's easier to sort after the fact.
2734
2544
        """
2735
 
        # When sorting, we usually have 10x more entries than directories. (69k
2736
 
        # total entries, 4k directories). So cache the results of splitting.
2737
 
        # Saving time and objects. Also, use StaticTuple to avoid putting all
2738
 
        # of these object into python's garbage collector.
2739
 
        split_dirs = {}
2740
 
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
 
2545
        def _key(entry):
2741
2546
            # sort by: directory parts, file name, file id
2742
 
            dirpath, fname, file_id = entry[0]
2743
 
            try:
2744
 
                split = _split_dirs[dirpath]
2745
 
            except KeyError:
2746
 
                split = _st.from_sequence(dirpath.split('/'))
2747
 
                _split_dirs[dirpath] = split
2748
 
            return _st(split, fname, file_id)
 
2547
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
2749
2548
        return sorted(entry_list, key=_key)
2750
2549
 
2751
2550
    def set_state_from_inventory(self, new_inv):
2876
2675
                        current_old[0][1].decode('utf8'))
2877
2676
                self._make_absent(current_old)
2878
2677
                current_old = advance(old_iterator)
2879
 
        self._mark_modified()
 
2678
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2880
2679
        self._id_index = None
2881
2680
        self._packed_stat_index = None
2882
2681
        if tracing:
2883
2682
            trace.mutter("set_state_from_inventory complete.")
2884
2683
 
2885
 
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
2886
 
        """Wipe the currently stored state and set it to something new.
2887
 
 
2888
 
        This is a hard-reset for the data we are working with.
2889
 
        """
2890
 
        # Technically, we really want a write lock, but until we write, we
2891
 
        # don't really need it.
2892
 
        self._requires_lock()
2893
 
        # root dir and root dir contents with no children. We have to have a
2894
 
        # root for set_state_from_inventory to work correctly.
2895
 
        empty_root = (('', '', inventory.ROOT_ID),
2896
 
                      [('d', '', 0, False, DirState.NULLSTAT)])
2897
 
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
2898
 
        self._set_data([], empty_tree_dirblocks)
2899
 
        self.set_state_from_inventory(working_inv)
2900
 
        self.set_parent_trees(parent_trees, parent_ghosts)
2901
 
 
2902
2684
    def _make_absent(self, current_old):
2903
2685
        """Mark current_old - an entry - as absent for tree 0.
2904
2686
 
2948
2730
            if update_tree_details[0][0] == 'a': # absent
2949
2731
                raise AssertionError('bad row %r' % (update_tree_details,))
2950
2732
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2951
 
        self._mark_modified()
 
2733
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2952
2734
        return last_reference
2953
2735
 
2954
2736
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2996
2778
                            # This entry has the same path (but a different id) as
2997
2779
                            # the new entry we're adding, and is present in ths
2998
2780
                            # tree.
2999
 
                            self._raise_invalid(
 
2781
                            raise errors.InconsistentDelta(
3000
2782
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
3001
2783
                                "Attempt to add item at path already occupied by "
3002
2784
                                "id %r" % entry[0][2])
3123
2905
            if not present:
3124
2906
                self._dirblocks.insert(block_index, (subdir_key[0], []))
3125
2907
 
3126
 
        self._mark_modified()
 
2908
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
3127
2909
 
3128
2910
    def _maybe_remove_row(self, block, index, id_index):
3129
2911
        """Remove index if it is absent or relocated across the row.
3355
3137
 
3356
3138
 
3357
3139
def py_update_entry(state, entry, abspath, stat_value,
3358
 
                 _stat_to_minikind=DirState._stat_to_minikind):
 
3140
                 _stat_to_minikind=DirState._stat_to_minikind,
 
3141
                 _pack_stat=pack_stat):
3359
3142
    """Update the entry based on what is actually on disk.
3360
3143
 
3361
3144
    This function only calculates the sha if it needs to - if the entry is
3374
3157
    except KeyError:
3375
3158
        # Unhandled kind
3376
3159
        return None
3377
 
    packed_stat = pack_stat(stat_value)
 
3160
    packed_stat = _pack_stat(stat_value)
3378
3161
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3379
3162
     saved_executable, saved_packed_stat) = entry[1][0]
3380
3163
 
3394
3177
    # If we have gotten this far, that means that we need to actually
3395
3178
    # process this entry.
3396
3179
    link_or_sha1 = None
3397
 
    worth_saving = True
3398
3180
    if minikind == 'f':
3399
3181
        executable = state._is_executable(stat_value.st_mode,
3400
3182
                                         saved_executable)
3416
3198
        else:
3417
3199
            entry[1][0] = ('f', '', stat_value.st_size,
3418
3200
                           executable, DirState.NULLSTAT)
3419
 
            worth_saving = False
3420
3201
    elif minikind == 'd':
3421
3202
        link_or_sha1 = None
3422
3203
        entry[1][0] = ('d', '', 0, False, packed_stat)
3428
3209
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3429
3210
            state._ensure_block(block_index, entry_index,
3430
3211
                               osutils.pathjoin(entry[0][0], entry[0][1]))
3431
 
        else:
3432
 
            worth_saving = False
3433
3212
    elif minikind == 'l':
3434
 
        if saved_minikind == 'l':
3435
 
            worth_saving = False
3436
3213
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3437
3214
        if state._cutoff_time is None:
3438
3215
            state._sha_cutoff_time()
3443
3220
        else:
3444
3221
            entry[1][0] = ('l', '', stat_value.st_size,
3445
3222
                           False, DirState.NULLSTAT)
3446
 
    if worth_saving:
3447
 
        state._mark_modified([entry])
 
3223
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
3448
3224
    return link_or_sha1
3449
3225
 
3450
3226
 
3759
3535
            raise AssertionError("don't know how to compare "
3760
3536
                "source_minikind=%r, target_minikind=%r"
3761
3537
                % (source_minikind, target_minikind))
 
3538
            ## import pdb;pdb.set_trace()
3762
3539
        return None, None
3763
3540
 
3764
3541
    def __iter__(self):
4253
4030
        _bisect_path_left,
4254
4031
        _bisect_path_right,
4255
4032
        cmp_by_dirs,
4256
 
        pack_stat,
4257
4033
        ProcessEntryC as _process_entry,
4258
4034
        update_entry as update_entry,
4259
4035
        )
4265
4041
        _bisect_path_left,
4266
4042
        _bisect_path_right,
4267
4043
        cmp_by_dirs,
4268
 
        pack_stat,
4269
4044
        )
4270
4045
    # FIXME: It would be nice to be able to track moved lines so that the
4271
4046
    # corresponding python code can be moved to the _dirstate_helpers_py