~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Andrew Bennetts
  • Date: 2010-10-08 08:15:14 UTC
  • mto: This revision was merged to the branch mainline in revision 5498.
  • Revision ID: andrew.bennetts@canonical.com-20101008081514-dviqzrdfwyzsqbz2
Split NEWS into per-release doc/en/release-notes/bzr-*.txt

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
 
                # The block where we want to put the file is not present.
1652
 
                # However, it might have just been an empty directory. Look for
1653
 
                # the parent in the basis-so-far before throwing an error.
1654
 
                parent_dir, parent_base = osutils.split(dirname)
1655
 
                parent_block_idx, parent_entry_idx, _, parent_present = \
1656
 
                    self._get_block_entry_index(parent_dir, parent_base, 1)
1657
 
                if not parent_present:
1658
 
                    self._raise_invalid(new_path, file_id,
1659
 
                        "Unable to find block for this record."
1660
 
                        " Was the parent added?")
1661
 
                self._ensure_block(parent_block_idx, parent_entry_idx, dirname)
1662
 
 
1663
 
            block = self._dirblocks[block_index][1]
1664
 
            entry_index, present = self._find_entry_index(entry_key, block)
1665
 
            if real_add:
1666
 
                if old_path is not None:
1667
 
                    self._raise_invalid(new_path, file_id,
1668
 
                        'considered a real add but still had old_path at %s'
1669
 
                        % (old_path,))
1670
 
            if present:
1671
 
                entry = block[entry_index]
1672
 
                basis_kind = entry[1][1][0]
1673
 
                if basis_kind == 'a':
1674
 
                    entry[1][1] = new_details
1675
 
                elif basis_kind == 'r':
1676
 
                    raise NotImplementedError()
1677
 
                else:
1678
 
                    self._raise_invalid(new_path, file_id,
1679
 
                        "An entry was marked as a new add"
1680
 
                        " but the basis target already existed")
1681
 
            else:
1682
 
                # The exact key was not found in the block. However, we need to
1683
 
                # check if there is a key next to us that would have matched.
1684
 
                # We only need to check 2 locations, because there are only 2
1685
 
                # trees present.
1686
 
                for maybe_index in range(entry_index-1, entry_index+1):
1687
 
                    if maybe_index < 0 or maybe_index >= len(block):
1688
 
                        continue
1689
 
                    maybe_entry = block[maybe_index]
1690
 
                    if maybe_entry[0][:2] != (dirname, basename):
1691
 
                        # Just a random neighbor
1692
 
                        continue
1693
 
                    if maybe_entry[0][2] == file_id:
1694
 
                        raise AssertionError(
1695
 
                            '_find_entry_index didnt find a key match'
1696
 
                            ' but walking the data did, for %s'
1697
 
                            % (entry_key,))
1698
 
                    basis_kind = maybe_entry[1][1][0]
1699
 
                    if basis_kind not in 'ar':
1700
 
                        self._raise_invalid(new_path, file_id,
1701
 
                            "we have an add record for path, but the path"
1702
 
                            " is already present with another file_id %s"
1703
 
                            % (maybe_entry[0][2],))
1704
 
 
1705
 
                entry = (entry_key, [DirState.NULL_PARENT_DETAILS,
1706
 
                                     new_details])
1707
 
                block.insert(entry_index, entry)
1708
 
 
1709
 
            active_kind = entry[1][0][0]
1710
 
            if active_kind == 'a':
1711
 
                # The active record shows up as absent, this could be genuine,
1712
 
                # or it could be present at some other location. We need to
1713
 
                # verify.
1714
 
                id_index = self._get_id_index()
1715
 
                # The id_index may not be perfectly accurate for tree1, because
1716
 
                # we haven't been keeping it updated. However, it should be
1717
 
                # fine for tree0, and that gives us enough info for what we
1718
 
                # need
1719
 
                keys = id_index.get(file_id, ())
1720
 
                for key in keys:
1721
 
                    block_i, entry_i, d_present, f_present = \
1722
 
                        self._get_block_entry_index(key[0], key[1], 0)
1723
 
                    if not f_present:
1724
 
                        continue
1725
 
                    active_entry = self._dirblocks[block_i][1][entry_i]
1726
 
                    if (active_entry[0][2] != file_id):
1727
 
                        # Some other file is at this path, we don't need to
1728
 
                        # link it.
1729
 
                        continue
1730
 
                    real_active_kind = active_entry[1][0][0]
1731
 
                    if real_active_kind in 'ar':
1732
 
                        # We found a record, which was not *this* record,
1733
 
                        # which matches the file_id, but is not actually
1734
 
                        # present. Something seems *really* wrong.
1735
 
                        self._raise_invalid(new_path, file_id,
1736
 
                            "We found a tree0 entry that doesnt make sense")
1737
 
                    # Now, we've found a tree0 entry which matches the file_id
1738
 
                    # but is at a different location. So update them to be
1739
 
                    # rename records.
1740
 
                    active_dir, active_name = active_entry[0][:2]
1741
 
                    if active_dir:
1742
 
                        active_path = active_dir + '/' + active_name
1743
 
                    else:
1744
 
                        active_path = active_name
1745
 
                    active_entry[1][1] = st('r', new_path, 0, False, '')
1746
 
                    entry[1][0] = st('r', active_path, 0, False, '')
1747
 
            elif active_kind == 'r':
1748
 
                raise NotImplementedError()
1749
 
 
1750
 
            new_kind = new_details[0]
1751
 
            if new_kind == 'd':
1752
 
                self._ensure_block(block_index, entry_index, new_path)
 
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
1753
1620
 
1754
1621
    def _update_basis_apply_changes(self, changes):
1755
1622
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1760
1627
        absent = 'ar'
1761
1628
        for old_path, new_path, file_id, new_details in changes:
1762
1629
            # the entry for this file_id must be in tree 0.
1763
 
            entry = self._get_entry(1, file_id, new_path)
1764
 
            if entry[0] is None or entry[1][1][0] in 'ar':
1765
 
                self._raise_invalid(new_path, file_id,
1766
 
                    'changed entry considered not present')
 
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')
1767
1640
            entry[1][1] = new_details
1768
1641
 
1769
1642
    def _update_basis_apply_deletes(self, deletes):
1781
1654
        null = DirState.NULL_PARENT_DETAILS
1782
1655
        for old_path, new_path, file_id, _, real_delete in deletes:
1783
1656
            if real_delete != (new_path is None):
1784
 
                self._raise_invalid(old_path, file_id, "bad delete delta")
 
1657
                self._changes_aborted = True
 
1658
                raise AssertionError("bad delete delta")
1785
1659
            # the entry for this file_id must be in tree 1.
1786
1660
            dirname, basename = osutils.split(old_path)
1787
1661
            block_index, entry_index, dir_present, file_present = \
1788
1662
                self._get_block_entry_index(dirname, basename, 1)
1789
1663
            if not file_present:
1790
 
                self._raise_invalid(old_path, file_id,
 
1664
                self._changes_aborted = True
 
1665
                raise errors.InconsistentDelta(old_path, file_id,
1791
1666
                    'basis tree does not contain removed entry')
1792
1667
            entry = self._dirblocks[block_index][1][entry_index]
1793
 
            # The state of the entry in the 'active' WT
1794
 
            active_kind = entry[1][0][0]
1795
1668
            if entry[0][2] != file_id:
1796
 
                self._raise_invalid(old_path, file_id,
 
1669
                self._changes_aborted = True
 
1670
                raise errors.InconsistentDelta(old_path, file_id,
1797
1671
                    'mismatched file_id in tree 1')
1798
 
            dir_block = ()
1799
 
            old_kind = entry[1][1][0]
1800
 
            if active_kind in 'ar':
1801
 
                # The active tree doesn't have this file_id.
1802
 
                # The basis tree is changing this record. If this is a
1803
 
                # rename, then we don't want the record here at all
1804
 
                # anymore. If it is just an in-place change, we want the
1805
 
                # record here, but we'll add it if we need to. So we just
1806
 
                # delete it
1807
 
                if active_kind == 'r':
1808
 
                    active_path = entry[1][0][1]
1809
 
                    active_entry = self._get_entry(0, file_id, active_path)
1810
 
                    if active_entry[1][1][0] != 'r':
1811
 
                        self._raise_invalid(old_path, file_id,
1812
 
                            "Dirstate did not have matching rename entries")
1813
 
                    elif active_entry[1][0][0] in 'ar':
1814
 
                        self._raise_invalid(old_path, file_id,
1815
 
                            "Dirstate had a rename pointing at an inactive"
1816
 
                            " tree0")
1817
 
                    active_entry[1][1] = null
 
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.')
1818
1678
                del self._dirblocks[block_index][1][entry_index]
1819
 
                if old_kind == 'd':
1820
 
                    # This was a directory, and the active tree says it
1821
 
                    # doesn't exist, and now the basis tree says it doesn't
1822
 
                    # exist. Remove its dirblock if present
1823
 
                    (dir_block_index,
1824
 
                     present) = self._find_block_index_from_key(
1825
 
                        (old_path, '', ''))
1826
 
                    if present:
1827
 
                        dir_block = self._dirblocks[dir_block_index][1]
1828
 
                        if not dir_block:
1829
 
                            # This entry is empty, go ahead and just remove it
1830
 
                            del self._dirblocks[dir_block_index]
1831
1679
            else:
1832
 
                # There is still an active record, so just mark this
1833
 
                # removed.
1834
 
                entry[1][1] = null
1835
 
                block_i, entry_i, d_present, f_present = \
1836
 
                    self._get_block_entry_index(old_path, '', 1)
1837
 
                if d_present:
1838
 
                    dir_block = self._dirblocks[block_i][1]
1839
 
            for child_entry in dir_block:
1840
 
                child_basis_kind = child_entry[1][1][0]
1841
 
                if child_basis_kind not in 'ar':
1842
 
                    self._raise_invalid(old_path, file_id,
1843
 
                        "The file id was deleted but its children were "
1844
 
                        "not deleted.")
 
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
1845
1695
 
1846
1696
    def _after_delta_check_parents(self, parents, index):
1847
1697
        """Check that parents required by the delta are all intact.
1856
1706
            # has the right file id.
1857
1707
            entry = self._get_entry(index, file_id, dirname_utf8)
1858
1708
            if entry[1] is None:
1859
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1709
                self._changes_aborted = True
 
1710
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1860
1711
                    file_id, "This parent is not present.")
1861
1712
            # Parents of things must be directories
1862
1713
            if entry[1][index][0] != 'd':
1863
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1714
                self._changes_aborted = True
 
1715
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1864
1716
                    file_id, "This parent is not a directory.")
1865
1717
 
1866
1718
    def _observed_sha1(self, entry, sha1, stat_value,
1867
 
        _stat_to_minikind=_stat_to_minikind):
 
1719
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
1868
1720
        """Note the sha1 of a file.
1869
1721
 
1870
1722
        :param entry: The entry the sha1 is for.
1876
1728
        except KeyError:
1877
1729
            # Unhandled kind
1878
1730
            return None
 
1731
        packed_stat = _pack_stat(stat_value)
1879
1732
        if minikind == 'f':
1880
1733
            if self._cutoff_time is None:
1881
1734
                self._sha_cutoff_time()
1882
1735
            if (stat_value.st_mtime < self._cutoff_time
1883
1736
                and stat_value.st_ctime < self._cutoff_time):
1884
 
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
1885
 
                               pack_stat(stat_value))
1886
 
                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
1887
1740
 
1888
1741
    def _sha_cutoff_time(self):
1889
1742
        """Return cutoff time.
1933
1786
            # paths are produced by UnicodeDirReader on purpose.
1934
1787
            abspath = abspath.encode(fs_encoding)
1935
1788
        target = os.readlink(abspath)
1936
 
        if fs_encoding not in ('utf-8', 'ascii'):
 
1789
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
1937
1790
            # Change encoding if needed
1938
1791
            target = target.decode(fs_encoding).encode('UTF-8')
1939
1792
        return target
1947
1800
        """Serialise the entire dirstate to a sequence of lines."""
1948
1801
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1949
1802
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1950
 
            # read what's on disk.
 
1803
            # read whats on disk.
1951
1804
            self._state_file.seek(0)
1952
1805
            return self._state_file.readlines()
1953
1806
        lines = []
1954
1807
        lines.append(self._get_parents_line(self.get_parent_ids()))
1955
1808
        lines.append(self._get_ghosts_line(self._ghosts))
1956
 
        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()))
1957
1811
        return self._get_output_lines(lines)
1958
1812
 
1959
1813
    def _get_ghosts_line(self, ghost_ids):
1964
1818
        """Create a line for the state file for parents information."""
1965
1819
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1966
1820
 
1967
 
    def _get_entry_lines(self):
1968
 
        """Create lines for entries."""
1969
 
        return map(self._entry_to_line, self._iter_entries())
1970
 
 
1971
1821
    def _get_fields_to_entry(self):
1972
1822
        """Get a function which converts entry fields into a entry record.
1973
1823
 
2091
1941
            entry_index += 1
2092
1942
        return block_index, entry_index, True, False
2093
1943
 
2094
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
2095
 
                   include_deleted=False):
 
1944
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
2096
1945
        """Get the dirstate entry for path in tree tree_index.
2097
1946
 
2098
1947
        If either file_id or path is supplied, it is used as the key to lookup.
2240
2089
            executable = False
2241
2090
        else:
2242
2091
            raise Exception("can't pack %s" % inv_entry)
2243
 
        return static_tuple.StaticTuple(minikind, fingerprint, size,
2244
 
                                        executable, tree_data)
 
2092
        return (minikind, fingerprint, size, executable, tree_data)
2245
2093
 
2246
2094
    def _iter_child_entries(self, tree_index, path_utf8):
2247
2095
        """Iterate over all the entries that are children of path_utf.
2297
2145
 
2298
2146
    def _get_id_index(self):
2299
2147
        """Get an id index of self._dirblocks.
2300
 
 
 
2148
        
2301
2149
        This maps from file_id => [(directory, name, file_id)] entries where
2302
2150
        that file_id appears in one of the trees.
2303
2151
        """
2317
2165
        # such, we use a simple tuple, and do our own uniqueness checks. While
2318
2166
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2319
2167
        # cause quadratic failure.
 
2168
        # TODO: This should use StaticTuple
2320
2169
        file_id = entry_key[2]
2321
2170
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2322
2171
        if file_id not in id_index:
2362
2211
        """The number of parent entries in each record row."""
2363
2212
        return len(self._parents) - len(self._ghosts)
2364
2213
 
2365
 
    @classmethod
2366
 
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
 
2214
    @staticmethod
 
2215
    def on_file(path, sha1_provider=None):
2367
2216
        """Construct a DirState on the file at path "path".
2368
2217
 
2369
2218
        :param path: The path at which the dirstate file on disk should live.
2370
2219
        :param sha1_provider: an object meeting the SHA1Provider interface.
2371
2220
            If None, a DefaultSHA1Provider is used.
2372
 
        :param worth_saving_limit: when the exact number of hash changed
2373
 
            entries is known, only bother saving the dirstate if more than
2374
 
            this count of entries have changed. -1 means never save.
2375
2221
        :return: An unlocked DirState object, associated with the given path.
2376
2222
        """
2377
2223
        if sha1_provider is None:
2378
2224
            sha1_provider = DefaultSHA1Provider()
2379
 
        result = cls(path, sha1_provider,
2380
 
                     worth_saving_limit=worth_saving_limit)
 
2225
        result = DirState(path, sha1_provider)
2381
2226
        return result
2382
2227
 
2383
2228
    def _read_dirblocks_if_needed(self):
2441
2286
            raise errors.BzrError('missing num_entries line')
2442
2287
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2443
2288
 
2444
 
    def sha1_from_stat(self, path, stat_result):
 
2289
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
2445
2290
        """Find a sha1 given a stat lookup."""
2446
 
        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)
2447
2292
 
2448
2293
    def _get_packed_stat_index(self):
2449
2294
        """Get a packed_stat index of self._dirblocks."""
2475
2320
            trace.mutter('Not saving DirState because '
2476
2321
                    '_changes_aborted is set.')
2477
2322
            return
2478
 
        # TODO: Since we now distinguish IN_MEMORY_MODIFIED from
2479
 
        #       IN_MEMORY_HASH_MODIFIED, we should only fail quietly if we fail
2480
 
        #       to save an IN_MEMORY_HASH_MODIFIED, and fail *noisily* if we
2481
 
        #       fail to save IN_MEMORY_MODIFIED
2482
 
        if not self._worth_saving():
2483
 
            return
 
2323
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
 
2324
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2484
2325
 
2485
 
        grabbed_write_lock = False
2486
 
        if self._lock_state != 'w':
2487
 
            grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
2488
 
            # Switch over to the new lock, as the old one may be closed.
2489
 
            # TODO: jam 20070315 We should validate the disk file has
2490
 
            #       not changed contents, since temporary_write_lock may
2491
 
            #       not be an atomic operation.
2492
 
            self._lock_token = new_lock
2493
 
            self._state_file = new_lock.f
2494
 
            if not grabbed_write_lock:
2495
 
                # We couldn't grab a write lock, so we switch back to a read one
2496
 
                return
2497
 
        try:
2498
 
            lines = self.get_lines()
2499
 
            self._state_file.seek(0)
2500
 
            self._state_file.writelines(lines)
2501
 
            self._state_file.truncate()
2502
 
            self._state_file.flush()
2503
 
            self._maybe_fdatasync()
2504
 
            self._mark_unmodified()
2505
 
        finally:
2506
 
            if grabbed_write_lock:
2507
 
                self._lock_token = self._lock_token.restore_read_lock()
2508
 
                self._state_file = self._lock_token.f
 
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.
2509
2330
                # TODO: jam 20070315 We should validate the disk file has
2510
 
                #       not changed contents. Since restore_read_lock may
2511
 
                #       not be an atomic operation.                
2512
 
 
2513
 
    def _maybe_fdatasync(self):
2514
 
        """Flush to disk if possible and if not configured off."""
2515
 
        if self._config_stack.get('dirstate.fdatasync'):
2516
 
            osutils.fdatasync(self._state_file.fileno())
2517
 
 
2518
 
    def _worth_saving(self):
2519
 
        """Is it worth saving the dirstate or not?"""
2520
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED
2521
 
            or self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2522
 
            return True
2523
 
        if self._dirblock_state == DirState.IN_MEMORY_HASH_MODIFIED:
2524
 
            if self._worth_saving_limit == -1:
2525
 
                # We never save hash changes when the limit is -1
2526
 
                return False
2527
 
            # If we're using smart saving and only a small number of
2528
 
            # entries have changed their hash, don't bother saving. John has
2529
 
            # suggested using a heuristic here based on the size of the
2530
 
            # changed files and/or tree. For now, we go with a configurable
2531
 
            # number of changes, keeping the calculation time
2532
 
            # as low overhead as possible. (This also keeps all existing
2533
 
            # tests passing as the default is 0, i.e. always save.)
2534
 
            if len(self._known_hash_changes) >= self._worth_saving_limit:
2535
 
                return True
2536
 
        return False
 
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.
2537
2352
 
2538
2353
    def _set_data(self, parent_ids, dirblocks):
2539
2354
        """Set the full dirstate data in memory.
2548
2363
        """
2549
2364
        # our memory copy is now authoritative.
2550
2365
        self._dirblocks = dirblocks
2551
 
        self._mark_modified(header_modified=True)
 
2366
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2367
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2552
2368
        self._parents = list(parent_ids)
2553
2369
        self._id_index = None
2554
2370
        self._packed_stat_index = None
2574
2390
        self._make_absent(entry)
2575
2391
        self.update_minimal(('', '', new_id), 'd',
2576
2392
            path_utf8='', packed_stat=entry[1][0][4])
2577
 
        self._mark_modified()
 
2393
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2578
2394
 
2579
2395
    def set_parent_trees(self, trees, ghosts):
2580
2396
        """Set the parent trees for the dirstate.
2625
2441
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2626
2442
        # how many trees do we end up with
2627
2443
        parent_count = len(parent_trees)
2628
 
        st = static_tuple.StaticTuple
2629
2444
 
2630
2445
        # one: the current tree
2631
2446
        for entry in self._iter_entries():
2648
2463
            # the suffix is from tree_index+1:parent_count+1.
2649
2464
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2650
2465
            # now stitch in all the entries from this tree
2651
 
            last_dirname = None
2652
 
            for path, entry in tree.iter_entries_by_dir():
 
2466
            for path, entry in tree.inventory.iter_entries_by_dir():
2653
2467
                # here we process each trees details for each item in the tree.
2654
2468
                # we first update any existing entries for the id at other paths,
2655
2469
                # then we either create or update the entry for the id at the
2662
2476
                file_id = entry.file_id
2663
2477
                path_utf8 = path.encode('utf8')
2664
2478
                dirname, basename = osutils.split(path_utf8)
2665
 
                if dirname == last_dirname:
2666
 
                    # Try to re-use objects as much as possible
2667
 
                    dirname = last_dirname
2668
 
                else:
2669
 
                    last_dirname = dirname
2670
 
                new_entry_key = st(dirname, basename, file_id)
 
2479
                new_entry_key = (dirname, basename, file_id)
2671
2480
                # tree index consistency: All other paths for this id in this tree
2672
2481
                # index must point to the correct path.
2673
 
                entry_keys = id_index.get(file_id, ())
2674
 
                for entry_key in entry_keys:
 
2482
                for entry_key in id_index.get(file_id, ()):
2675
2483
                    # TODO:PROFILING: It might be faster to just update
2676
2484
                    # rather than checking if we need to, and then overwrite
2677
2485
                    # the one we are located at.
2680
2488
                        # other trees, so put absent pointers there
2681
2489
                        # This is the vertical axis in the matrix, all pointing
2682
2490
                        # to the real path.
2683
 
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
2684
 
                                                            False, '')
2685
 
                # by path consistency: Insert into an existing path record
2686
 
                # (trivial), or add a new one with relocation pointers for the
2687
 
                # other tree indexes.
 
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, ())
2688
2495
                if new_entry_key in entry_keys:
2689
 
                    # there is already an entry where this data belongs, just
2690
 
                    # insert it.
 
2496
                    # there is already an entry where this data belongs, just insert it.
2691
2497
                    by_path[new_entry_key][tree_index] = \
2692
2498
                        self._inv_entry_to_details(entry)
2693
2499
                else:
2703
2509
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2704
2510
                        else:
2705
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.
2706
2515
                            a_key = iter(entry_keys).next()
2707
2516
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2708
 
                                # its a pointer or missing statement, use it as
2709
 
                                # is.
 
2517
                                # its a pointer or missing statement, use it as is.
2710
2518
                                new_details.append(by_path[a_key][lookup_index])
2711
2519
                            else:
2712
2520
                                # we have the right key, make a pointer to it.
2713
2521
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2714
 
                                new_details.append(st('r', real_path, 0, False,
2715
 
                                                      ''))
 
2522
                                new_details.append(('r', real_path, 0, False, ''))
2716
2523
                    new_details.append(self._inv_entry_to_details(entry))
2717
2524
                    new_details.extend(new_location_suffix)
2718
2525
                    by_path[new_entry_key] = new_details
2724
2531
        self._entries_to_current_state(new_entries)
2725
2532
        self._parents = [rev_id for rev_id, tree in trees]
2726
2533
        self._ghosts = list(ghosts)
2727
 
        self._mark_modified(header_modified=True)
 
2534
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2535
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2728
2536
        self._id_index = id_index
2729
2537
 
2730
2538
    def _sort_entries(self, entry_list):
2734
2542
        try to keep everything in sorted blocks all the time, but sometimes
2735
2543
        it's easier to sort after the fact.
2736
2544
        """
2737
 
        # When sorting, we usually have 10x more entries than directories. (69k
2738
 
        # total entries, 4k directories). So cache the results of splitting.
2739
 
        # Saving time and objects. Also, use StaticTuple to avoid putting all
2740
 
        # of these object into python's garbage collector.
2741
 
        split_dirs = {}
2742
 
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
 
2545
        def _key(entry):
2743
2546
            # sort by: directory parts, file name, file id
2744
 
            dirpath, fname, file_id = entry[0]
2745
 
            try:
2746
 
                split = _split_dirs[dirpath]
2747
 
            except KeyError:
2748
 
                split = _st.from_sequence(dirpath.split('/'))
2749
 
                _split_dirs[dirpath] = split
2750
 
            return _st(split, fname, file_id)
 
2547
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
2751
2548
        return sorted(entry_list, key=_key)
2752
2549
 
2753
2550
    def set_state_from_inventory(self, new_inv):
2878
2675
                        current_old[0][1].decode('utf8'))
2879
2676
                self._make_absent(current_old)
2880
2677
                current_old = advance(old_iterator)
2881
 
        self._mark_modified()
 
2678
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2882
2679
        self._id_index = None
2883
2680
        self._packed_stat_index = None
2884
2681
        if tracing:
2885
2682
            trace.mutter("set_state_from_inventory complete.")
2886
2683
 
2887
 
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
2888
 
        """Wipe the currently stored state and set it to something new.
2889
 
 
2890
 
        This is a hard-reset for the data we are working with.
2891
 
        """
2892
 
        # Technically, we really want a write lock, but until we write, we
2893
 
        # don't really need it.
2894
 
        self._requires_lock()
2895
 
        # root dir and root dir contents with no children. We have to have a
2896
 
        # root for set_state_from_inventory to work correctly.
2897
 
        empty_root = (('', '', inventory.ROOT_ID),
2898
 
                      [('d', '', 0, False, DirState.NULLSTAT)])
2899
 
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
2900
 
        self._set_data([], empty_tree_dirblocks)
2901
 
        self.set_state_from_inventory(working_inv)
2902
 
        self.set_parent_trees(parent_trees, parent_ghosts)
2903
 
 
2904
2684
    def _make_absent(self, current_old):
2905
2685
        """Mark current_old - an entry - as absent for tree 0.
2906
2686
 
2950
2730
            if update_tree_details[0][0] == 'a': # absent
2951
2731
                raise AssertionError('bad row %r' % (update_tree_details,))
2952
2732
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2953
 
        self._mark_modified()
 
2733
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2954
2734
        return last_reference
2955
2735
 
2956
2736
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2998
2778
                            # This entry has the same path (but a different id) as
2999
2779
                            # the new entry we're adding, and is present in ths
3000
2780
                            # tree.
3001
 
                            self._raise_invalid(
 
2781
                            raise errors.InconsistentDelta(
3002
2782
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
3003
2783
                                "Attempt to add item at path already occupied by "
3004
2784
                                "id %r" % entry[0][2])
3125
2905
            if not present:
3126
2906
                self._dirblocks.insert(block_index, (subdir_key[0], []))
3127
2907
 
3128
 
        self._mark_modified()
 
2908
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
3129
2909
 
3130
2910
    def _maybe_remove_row(self, block, index, id_index):
3131
2911
        """Remove index if it is absent or relocated across the row.
3287
3067
        if self._id_index is not None:
3288
3068
            for file_id, entry_keys in self._id_index.iteritems():
3289
3069
                for entry_key in entry_keys:
3290
 
                    # Check that the entry in the map is pointing to the same
3291
 
                    # file_id
3292
3070
                    if entry_key[2] != file_id:
3293
3071
                        raise AssertionError(
3294
3072
                            'file_id %r did not match entry key %s'
3295
3073
                            % (file_id, entry_key))
3296
 
                    # And that from this entry key, we can look up the original
3297
 
                    # record
3298
 
                    block_index, present = self._find_block_index_from_key(entry_key)
3299
 
                    if not present:
3300
 
                        raise AssertionError('missing block for entry key: %r', entry_key)
3301
 
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
3302
 
                    if not present:
3303
 
                        raise AssertionError('missing entry for key: %r', entry_key)
3304
3074
                if len(entry_keys) != len(set(entry_keys)):
3305
3075
                    raise AssertionError(
3306
3076
                        'id_index contained non-unique data for %s'
3367
3137
 
3368
3138
 
3369
3139
def py_update_entry(state, entry, abspath, stat_value,
3370
 
                 _stat_to_minikind=DirState._stat_to_minikind):
 
3140
                 _stat_to_minikind=DirState._stat_to_minikind,
 
3141
                 _pack_stat=pack_stat):
3371
3142
    """Update the entry based on what is actually on disk.
3372
3143
 
3373
3144
    This function only calculates the sha if it needs to - if the entry is
3386
3157
    except KeyError:
3387
3158
        # Unhandled kind
3388
3159
        return None
3389
 
    packed_stat = pack_stat(stat_value)
 
3160
    packed_stat = _pack_stat(stat_value)
3390
3161
    (saved_minikind, saved_link_or_sha1, saved_file_size,
3391
3162
     saved_executable, saved_packed_stat) = entry[1][0]
3392
3163
 
3406
3177
    # If we have gotten this far, that means that we need to actually
3407
3178
    # process this entry.
3408
3179
    link_or_sha1 = None
3409
 
    worth_saving = True
3410
3180
    if minikind == 'f':
3411
3181
        executable = state._is_executable(stat_value.st_mode,
3412
3182
                                         saved_executable)
3428
3198
        else:
3429
3199
            entry[1][0] = ('f', '', stat_value.st_size,
3430
3200
                           executable, DirState.NULLSTAT)
3431
 
            worth_saving = False
3432
3201
    elif minikind == 'd':
3433
3202
        link_or_sha1 = None
3434
3203
        entry[1][0] = ('d', '', 0, False, packed_stat)
3440
3209
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3441
3210
            state._ensure_block(block_index, entry_index,
3442
3211
                               osutils.pathjoin(entry[0][0], entry[0][1]))
3443
 
        else:
3444
 
            worth_saving = False
3445
3212
    elif minikind == 'l':
3446
 
        if saved_minikind == 'l':
3447
 
            worth_saving = False
3448
3213
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3449
3214
        if state._cutoff_time is None:
3450
3215
            state._sha_cutoff_time()
3455
3220
        else:
3456
3221
            entry[1][0] = ('l', '', stat_value.st_size,
3457
3222
                           False, DirState.NULLSTAT)
3458
 
    if worth_saving:
3459
 
        state._mark_modified([entry])
 
3223
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
3460
3224
    return link_or_sha1
3461
3225
 
3462
3226
 
3771
3535
            raise AssertionError("don't know how to compare "
3772
3536
                "source_minikind=%r, target_minikind=%r"
3773
3537
                % (source_minikind, target_minikind))
 
3538
            ## import pdb;pdb.set_trace()
3774
3539
        return None, None
3775
3540
 
3776
3541
    def __iter__(self):
4265
4030
        _bisect_path_left,
4266
4031
        _bisect_path_right,
4267
4032
        cmp_by_dirs,
4268
 
        pack_stat,
4269
4033
        ProcessEntryC as _process_entry,
4270
4034
        update_entry as update_entry,
4271
4035
        )
4277
4041
        _bisect_path_left,
4278
4042
        _bisect_path_right,
4279
4043
        cmp_by_dirs,
4280
 
        pack_stat,
4281
4044
        )
4282
4045
    # FIXME: It would be nice to be able to track moved lines so that the
4283
4046
    # corresponding python code can be moved to the _dirstate_helpers_py