~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-05-11 11:47:36 UTC
  • mfrom: (5200.3.8 lock_return)
  • Revision ID: pqm@pqm.ubuntu.com-20100511114736-mc1sq9zyo3vufec7
(lifeless) Provide a consistent interface to Tree, Branch,
 Repository where lock methods return an object with an unlock method to
 unlock the lock. This breaks the API for Branch,
 Repository on their lock_write methods. (Robert Collins)

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
232
215
 
233
216
from bzrlib import (
234
217
    cache_utf8,
235
 
    config,
236
218
    debug,
237
219
    errors,
238
220
    inventory,
239
221
    lock,
240
222
    osutils,
241
 
    static_tuple,
242
223
    trace,
243
 
    urlutils,
244
224
    )
245
225
 
246
226
 
284
264
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
285
265
 
286
266
 
287
 
def _unpack_stat(packed_stat):
288
 
    """Turn a packed_stat back into the stat fields.
289
 
 
290
 
    This is meant as a debugging tool, should not be used in real code.
291
 
    """
292
 
    (st_size, st_mtime, st_ctime, st_dev, st_ino,
293
 
     st_mode) = struct.unpack('>LLLLLL', binascii.a2b_base64(packed_stat))
294
 
    return dict(st_size=st_size, st_mtime=st_mtime, st_ctime=st_ctime,
295
 
                st_dev=st_dev, st_ino=st_ino, st_mode=st_mode)
296
 
 
297
 
 
298
267
class SHA1Provider(object):
299
268
    """An interface for getting sha1s of a file."""
300
269
 
385
354
    NOT_IN_MEMORY = 0
386
355
    IN_MEMORY_UNMODIFIED = 1
387
356
    IN_MEMORY_MODIFIED = 2
388
 
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
389
357
 
390
358
    # A pack_stat (the x's) that is just noise and will never match the output
391
359
    # of base64 encode.
392
360
    NULLSTAT = 'x' * 32
393
 
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
 
361
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
394
362
 
395
363
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
396
364
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
397
365
 
398
 
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
 
366
    def __init__(self, path, sha1_provider):
399
367
        """Create a  DirState object.
400
368
 
401
369
        :param path: The path at which the dirstate file on disk should live.
402
370
        :param sha1_provider: an object meeting the SHA1Provider interface.
403
 
        :param worth_saving_limit: when the exact number of hash changed
404
 
            entries is known, only bother saving the dirstate if more than
405
 
            this count of entries have changed.
406
 
            -1 means never save hash changes, 0 means always save hash changes.
407
371
        """
408
372
        # _header_state and _dirblock_state represent the current state
409
373
        # of the dirstate metadata and the per-row data respectiely.
446
410
        # during commit.
447
411
        self._last_block_index = None
448
412
        self._last_entry_index = None
449
 
        # The set of known hash changes
450
 
        self._known_hash_changes = set()
451
 
        # How many hash changed entries can we have without saving
452
 
        self._worth_saving_limit = worth_saving_limit
453
 
        self._config_stack = config.LocationStack(urlutils.local_path_to_url(
454
 
            path))
455
413
 
456
414
    def __repr__(self):
457
415
        return "%s(%r)" % \
458
416
            (self.__class__.__name__, self._filename)
459
417
 
460
 
    def _mark_modified(self, hash_changed_entries=None, header_modified=False):
461
 
        """Mark this dirstate as modified.
462
 
 
463
 
        :param hash_changed_entries: if non-None, mark just these entries as
464
 
            having their hash modified.
465
 
        :param header_modified: mark the header modified as well, not just the
466
 
            dirblocks.
467
 
        """
468
 
        #trace.mutter_callsite(3, "modified hash entries: %s", hash_changed_entries)
469
 
        if hash_changed_entries:
470
 
            self._known_hash_changes.update([e[0] for e in hash_changed_entries])
471
 
            if self._dirblock_state in (DirState.NOT_IN_MEMORY,
472
 
                                        DirState.IN_MEMORY_UNMODIFIED):
473
 
                # If the dirstate is already marked a IN_MEMORY_MODIFIED, then
474
 
                # that takes precedence.
475
 
                self._dirblock_state = DirState.IN_MEMORY_HASH_MODIFIED
476
 
        else:
477
 
            # TODO: Since we now have a IN_MEMORY_HASH_MODIFIED state, we
478
 
            #       should fail noisily if someone tries to set
479
 
            #       IN_MEMORY_MODIFIED but we don't have a write-lock!
480
 
            # We don't know exactly what changed so disable smart saving
481
 
            self._dirblock_state = DirState.IN_MEMORY_MODIFIED
482
 
        if header_modified:
483
 
            self._header_state = DirState.IN_MEMORY_MODIFIED
484
 
 
485
 
    def _mark_unmodified(self):
486
 
        """Mark this dirstate as unmodified."""
487
 
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
488
 
        self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
489
 
        self._known_hash_changes = set()
490
 
 
491
418
    def add(self, path, file_id, kind, stat, fingerprint):
492
419
        """Add a path to be tracked.
493
420
 
619
546
        if kind == 'directory':
620
547
           # insert a new dirblock
621
548
           self._ensure_block(block_index, entry_index, utf8path)
622
 
        self._mark_modified()
 
549
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
623
550
        if self._id_index:
624
 
            self._add_to_id_index(self._id_index, entry_key)
 
551
            self._id_index.setdefault(entry_key[2], set()).add(entry_key)
625
552
 
626
553
    def _bisect(self, paths):
627
554
        """Bisect through the disk structure for specific rows.
1091
1018
 
1092
1019
        self._ghosts = []
1093
1020
        self._parents = [parents[0]]
1094
 
        self._mark_modified(header_modified=True)
 
1021
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1022
        self._header_state = DirState.IN_MEMORY_MODIFIED
1095
1023
 
1096
1024
    def _empty_parent_info(self):
1097
1025
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1226
1154
    def _fields_per_entry(self):
1227
1155
        """How many null separated fields should be in each entry row.
1228
1156
 
1229
 
        Each line now has an extra '\\n' field which is not used
 
1157
        Each line now has an extra '\n' field which is not used
1230
1158
        so we just skip over it
1231
 
 
1232
 
        entry size::
 
1159
        entry size:
1233
1160
            3 fields for the key
1234
1161
            + number of fields per tree_data (5) * tree count
1235
1162
            + newline
1348
1275
            raise
1349
1276
        return result
1350
1277
 
1351
 
    def _check_delta_is_valid(self, delta):
1352
 
        return list(inventory._check_delta_unique_ids(
1353
 
                    inventory._check_delta_unique_old_paths(
1354
 
                    inventory._check_delta_unique_new_paths(
1355
 
                    inventory._check_delta_ids_match_entry(
1356
 
                    inventory._check_delta_ids_are_valid(
1357
 
                    inventory._check_delta_new_path_entry_both_or_None(delta)))))))
1358
 
 
1359
1278
    def update_by_delta(self, delta):
1360
1279
        """Apply an inventory delta to the dirstate for tree 0
1361
1280
 
1379
1298
        new_ids = set()
1380
1299
        # This loop transforms the delta to single atomic operations that can
1381
1300
        # be executed and validated.
1382
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1383
 
        for old_path, new_path, file_id, inv_entry in delta:
 
1301
        for old_path, new_path, file_id, inv_entry in sorted(
 
1302
            inventory._check_delta_unique_old_paths(
 
1303
            inventory._check_delta_unique_new_paths(
 
1304
            inventory._check_delta_ids_match_entry(
 
1305
            inventory._check_delta_ids_are_valid(
 
1306
            inventory._check_delta_new_path_entry_both_or_None(delta))))),
 
1307
            reverse=True):
1384
1308
            if (file_id in insertions) or (file_id in removals):
1385
 
                self._raise_invalid(old_path or new_path, file_id,
 
1309
                raise errors.InconsistentDelta(old_path or new_path, file_id,
1386
1310
                    "repeated file_id")
1387
1311
            if old_path is not None:
1388
1312
                old_path = old_path.encode('utf-8')
1391
1315
                new_ids.add(file_id)
1392
1316
            if new_path is not None:
1393
1317
                if inv_entry is None:
1394
 
                    self._raise_invalid(new_path, file_id,
 
1318
                    raise errors.InconsistentDelta(new_path, file_id,
1395
1319
                        "new_path with no entry")
1396
1320
                new_path = new_path.encode('utf-8')
1397
1321
                dirname_utf8, basename = osutils.split(new_path)
1438
1362
            # _get_entry raises BzrError when a request is inconsistent; we
1439
1363
            # want such errors to be shown as InconsistentDelta - and that 
1440
1364
            # fits the behaviour we trigger.
1441
 
            raise errors.InconsistentDeltaDelta(delta,
1442
 
                "error from _get_entry. %s" % (e,))
 
1365
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1443
1366
 
1444
1367
    def _apply_removals(self, removals):
1445
1368
        for file_id, path in sorted(removals, reverse=True,
1450
1373
            try:
1451
1374
                entry = self._dirblocks[block_i][1][entry_i]
1452
1375
            except IndexError:
1453
 
                self._raise_invalid(path, file_id,
 
1376
                self._changes_aborted = True
 
1377
                raise errors.InconsistentDelta(path, file_id,
1454
1378
                    "Wrong path for old path.")
1455
1379
            if not f_present or entry[1][0][0] in 'ar':
1456
 
                self._raise_invalid(path, file_id,
 
1380
                self._changes_aborted = True
 
1381
                raise errors.InconsistentDelta(path, file_id,
1457
1382
                    "Wrong path for old path.")
1458
1383
            if file_id != entry[0][2]:
1459
 
                self._raise_invalid(path, file_id,
 
1384
                self._changes_aborted = True
 
1385
                raise errors.InconsistentDelta(path, file_id,
1460
1386
                    "Attempt to remove path has wrong id - found %r."
1461
1387
                    % entry[0][2])
1462
1388
            self._make_absent(entry)
1472
1398
                # be due to it being in a parent tree, or a corrupt delta.
1473
1399
                for child_entry in self._dirblocks[block_i][1]:
1474
1400
                    if child_entry[1][0][0] not in ('r', 'a'):
1475
 
                        self._raise_invalid(path, entry[0][2],
 
1401
                        self._changes_aborted = True
 
1402
                        raise errors.InconsistentDelta(path, entry[0][2],
1476
1403
                            "The file id was deleted but its children were "
1477
1404
                            "not deleted.")
1478
1405
 
1482
1409
                self.update_minimal(key, minikind, executable, fingerprint,
1483
1410
                                    path_utf8=path_utf8)
1484
1411
        except errors.NotVersionedError:
1485
 
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
 
1412
            self._changes_aborted = True
 
1413
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
1486
1414
                "Missing parent")
1487
1415
 
1488
1416
    def update_basis_by_delta(self, delta, new_revid):
1496
1424
        Note that an exception during the operation of this method will leave
1497
1425
        the dirstate in a corrupt state where it should not be saved.
1498
1426
 
 
1427
        Finally, we expect all changes to be synchronising the basis tree with
 
1428
        the working tree.
 
1429
 
1499
1430
        :param new_revid: The new revision id for the trees parent.
1500
1431
        :param delta: An inventory delta (see apply_inventory_delta) describing
1501
1432
            the changes from the current left most parent revision to new_revid.
1513
1444
 
1514
1445
        self._parents[0] = new_revid
1515
1446
 
1516
 
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1447
        delta = sorted(delta, reverse=True)
1517
1448
        adds = []
1518
1449
        changes = []
1519
1450
        deletes = []
1540
1471
        new_ids = set()
1541
1472
        for old_path, new_path, file_id, inv_entry in delta:
1542
1473
            if inv_entry is not None and file_id != inv_entry.file_id:
1543
 
                self._raise_invalid(new_path, file_id,
 
1474
                raise errors.InconsistentDelta(new_path, file_id,
1544
1475
                    "mismatched entry file_id %r" % inv_entry)
1545
 
            if new_path is None:
1546
 
                new_path_utf8 = None
1547
 
            else:
 
1476
            if new_path is not None:
1548
1477
                if inv_entry is None:
1549
 
                    self._raise_invalid(new_path, file_id,
 
1478
                    raise errors.InconsistentDelta(new_path, file_id,
1550
1479
                        "new_path with no entry")
1551
1480
                new_path_utf8 = encode(new_path)
1552
1481
                # note the parent for validation
1554
1483
                if basename_utf8:
1555
1484
                    parents.add((dirname_utf8, inv_entry.parent_id))
1556
1485
            if old_path is None:
1557
 
                old_path_utf8 = None
1558
 
            else:
1559
 
                old_path_utf8 = encode(old_path)
1560
 
            if old_path is None:
1561
 
                adds.append((None, new_path_utf8, file_id,
 
1486
                adds.append((None, encode(new_path), file_id,
1562
1487
                    inv_to_entry(inv_entry), True))
1563
1488
                new_ids.add(file_id)
1564
1489
            elif new_path is None:
1565
 
                deletes.append((old_path_utf8, None, file_id, None, True))
1566
 
            elif (old_path, new_path) == root_only:
1567
 
                # change things in-place
1568
 
                # Note: the case of a parent directory changing its file_id
1569
 
                #       tends to break optimizations here, because officially
1570
 
                #       the file has actually been moved, it just happens to
1571
 
                #       end up at the same path. If we can figure out how to
1572
 
                #       handle that case, we can avoid a lot of add+delete
1573
 
                #       pairs for objects that stay put.
1574
 
                # elif old_path == new_path:
1575
 
                changes.append((old_path_utf8, new_path_utf8, file_id,
1576
 
                                inv_to_entry(inv_entry)))
1577
 
            else:
 
1490
                deletes.append((encode(old_path), None, file_id, None, True))
 
1491
            elif (old_path, new_path) != root_only:
1578
1492
                # Renames:
1579
1493
                # Because renames must preserve their children we must have
1580
1494
                # processed all relocations and removes before hand. The sort
1590
1504
                self._update_basis_apply_deletes(deletes)
1591
1505
                deletes = []
1592
1506
                # Split into an add/delete pair recursively.
1593
 
                adds.append((old_path_utf8, new_path_utf8, file_id,
1594
 
                             inv_to_entry(inv_entry), False))
 
1507
                adds.append((None, new_path_utf8, file_id,
 
1508
                    inv_to_entry(inv_entry), False))
1595
1509
                # Expunge deletes that we've seen so that deleted/renamed
1596
1510
                # children of a rename directory are handled correctly.
1597
 
                new_deletes = reversed(list(
1598
 
                    self._iter_child_entries(1, old_path_utf8)))
 
1511
                new_deletes = reversed(list(self._iter_child_entries(1,
 
1512
                    encode(old_path))))
1599
1513
                # Remove the current contents of the tree at orig_path, and
1600
1514
                # reinsert at the correct new path.
1601
1515
                for entry in new_deletes:
1602
 
                    child_dirname, child_basename, child_file_id = entry[0]
1603
 
                    if child_dirname:
1604
 
                        source_path = child_dirname + '/' + child_basename
 
1516
                    if entry[0][0]:
 
1517
                        source_path = entry[0][0] + '/' + entry[0][1]
1605
1518
                    else:
1606
 
                        source_path = child_basename
 
1519
                        source_path = entry[0][1]
1607
1520
                    if new_path_utf8:
1608
1521
                        target_path = new_path_utf8 + source_path[len(old_path):]
1609
1522
                    else:
1610
1523
                        if old_path == '':
1611
1524
                            raise AssertionError("cannot rename directory to"
1612
 
                                                 " itself")
 
1525
                                " itself")
1613
1526
                        target_path = source_path[len(old_path) + 1:]
1614
1527
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1615
1528
                    deletes.append(
1616
1529
                        (source_path, target_path, entry[0][2], None, False))
1617
 
                deletes.append((old_path_utf8, new_path, file_id, None, False))
 
1530
                deletes.append(
 
1531
                    (encode(old_path), new_path, file_id, None, False))
 
1532
            else:
 
1533
                # changes to just the root should not require remove/insertion
 
1534
                # of everything.
 
1535
                changes.append((encode(old_path), encode(new_path), file_id,
 
1536
                    inv_to_entry(inv_entry)))
1618
1537
        self._check_delta_ids_absent(new_ids, delta, 1)
1619
1538
        try:
1620
1539
            # Finish expunging deletes/first half of renames.
1630
1549
            if 'integrity error' not in str(e):
1631
1550
                raise
1632
1551
            # _get_entry raises BzrError when a request is inconsistent; we
1633
 
            # want such errors to be shown as InconsistentDelta - and that
1634
 
            # fits the behaviour we trigger.
1635
 
            raise errors.InconsistentDeltaDelta(delta,
1636
 
                "error from _get_entry. %s" % (e,))
 
1552
            # want such errors to be shown as InconsistentDelta - and that 
 
1553
            # fits the behaviour we trigger. Partof this is driven by dirstate
 
1554
            # only supporting deltas that turn the basis into a closer fit to
 
1555
            # the active tree.
 
1556
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1637
1557
 
1638
 
        self._mark_modified(header_modified=True)
 
1558
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1559
        self._header_state = DirState.IN_MEMORY_MODIFIED
1639
1560
        self._id_index = None
1640
1561
        return
1641
1562
 
1645
1566
            return
1646
1567
        id_index = self._get_id_index()
1647
1568
        for file_id in new_ids:
1648
 
            for key in id_index.get(file_id, ()):
 
1569
            for key in id_index.get(file_id, []):
1649
1570
                block_i, entry_i, d_present, f_present = \
1650
1571
                    self._get_block_entry_index(key[0], key[1], tree_index)
1651
1572
                if not f_present:
1655
1576
                if entry[0][2] != file_id:
1656
1577
                    # Different file_id, so not what we want.
1657
1578
                    continue
1658
 
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
 
1579
                # NB: No changes made before this helper is called, so no need
 
1580
                # to set the _changes_aborted flag.
 
1581
                raise errors.InconsistentDelta(
 
1582
                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
1659
1583
                    "This file_id is new in the delta but already present in "
1660
1584
                    "the target")
1661
1585
 
1662
 
    def _raise_invalid(self, path, file_id, reason):
1663
 
        self._changes_aborted = True
1664
 
        raise errors.InconsistentDelta(path, file_id, reason)
1665
 
 
1666
1586
    def _update_basis_apply_adds(self, adds):
1667
1587
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1668
1588
 
1676
1596
        """
1677
1597
        # Adds are accumulated partly from renames, so can be in any input
1678
1598
        # order - sort it.
1679
 
        # TODO: we may want to sort in dirblocks order. That way each entry
1680
 
        #       will end up in the same directory, allowing the _get_entry
1681
 
        #       fast-path for looking up 2 items in the same dir work.
1682
 
        adds.sort(key=lambda x: x[1])
 
1599
        adds.sort()
1683
1600
        # adds is now in lexographic order, which places all parents before
1684
1601
        # their children, so we can process it linearly.
1685
1602
        absent = 'ar'
1686
 
        st = static_tuple.StaticTuple
1687
1603
        for old_path, new_path, file_id, new_details, real_add in adds:
1688
 
            dirname, basename = osutils.split(new_path)
1689
 
            entry_key = st(dirname, basename, file_id)
1690
 
            block_index, present = self._find_block_index_from_key(entry_key)
1691
 
            if not present:
1692
 
                self._raise_invalid(new_path, file_id,
1693
 
                    "Unable to find block for this record."
1694
 
                    " Was the parent added?")
1695
 
            block = self._dirblocks[block_index][1]
1696
 
            entry_index, present = self._find_entry_index(entry_key, block)
1697
 
            if real_add:
1698
 
                if old_path is not None:
1699
 
                    self._raise_invalid(new_path, file_id,
1700
 
                        'considered a real add but still had old_path at %s'
1701
 
                        % (old_path,))
1702
 
            if present:
1703
 
                entry = block[entry_index]
1704
 
                basis_kind = entry[1][1][0]
1705
 
                if basis_kind == 'a':
1706
 
                    entry[1][1] = new_details
1707
 
                elif basis_kind == 'r':
1708
 
                    raise NotImplementedError()
1709
 
                else:
1710
 
                    self._raise_invalid(new_path, file_id,
1711
 
                        "An entry was marked as a new add"
1712
 
                        " but the basis target already existed")
1713
 
            else:
1714
 
                # The exact key was not found in the block. However, we need to
1715
 
                # check if there is a key next to us that would have matched.
1716
 
                # We only need to check 2 locations, because there are only 2
1717
 
                # trees present.
1718
 
                for maybe_index in range(entry_index-1, entry_index+1):
1719
 
                    if maybe_index < 0 or maybe_index >= len(block):
1720
 
                        continue
1721
 
                    maybe_entry = block[maybe_index]
1722
 
                    if maybe_entry[0][:2] != (dirname, basename):
1723
 
                        # Just a random neighbor
1724
 
                        continue
1725
 
                    if maybe_entry[0][2] == file_id:
1726
 
                        raise AssertionError(
1727
 
                            '_find_entry_index didnt find a key match'
1728
 
                            ' but walking the data did, for %s'
1729
 
                            % (entry_key,))
1730
 
                    basis_kind = maybe_entry[1][1][0]
1731
 
                    if basis_kind not in 'ar':
1732
 
                        self._raise_invalid(new_path, file_id,
1733
 
                            "we have an add record for path, but the path"
1734
 
                            " is already present with another file_id %s"
1735
 
                            % (maybe_entry[0][2],))
1736
 
 
1737
 
                entry = (entry_key, [DirState.NULL_PARENT_DETAILS,
1738
 
                                     new_details])
1739
 
                block.insert(entry_index, entry)
1740
 
 
1741
 
            active_kind = entry[1][0][0]
1742
 
            if active_kind == 'a':
1743
 
                # The active record shows up as absent, this could be genuine,
1744
 
                # or it could be present at some other location. We need to
1745
 
                # verify.
1746
 
                id_index = self._get_id_index()
1747
 
                # The id_index may not be perfectly accurate for tree1, because
1748
 
                # we haven't been keeping it updated. However, it should be
1749
 
                # fine for tree0, and that gives us enough info for what we
1750
 
                # need
1751
 
                keys = id_index.get(file_id, ())
1752
 
                for key in keys:
1753
 
                    block_i, entry_i, d_present, f_present = \
1754
 
                        self._get_block_entry_index(key[0], key[1], 0)
1755
 
                    if not f_present:
1756
 
                        continue
1757
 
                    active_entry = self._dirblocks[block_i][1][entry_i]
1758
 
                    if (active_entry[0][2] != file_id):
1759
 
                        # Some other file is at this path, we don't need to
1760
 
                        # link it.
1761
 
                        continue
1762
 
                    real_active_kind = active_entry[1][0][0]
1763
 
                    if real_active_kind in 'ar':
1764
 
                        # We found a record, which was not *this* record,
1765
 
                        # which matches the file_id, but is not actually
1766
 
                        # present. Something seems *really* wrong.
1767
 
                        self._raise_invalid(new_path, file_id,
1768
 
                            "We found a tree0 entry that doesnt make sense")
1769
 
                    # Now, we've found a tree0 entry which matches the file_id
1770
 
                    # but is at a different location. So update them to be
1771
 
                    # rename records.
1772
 
                    active_dir, active_name = active_entry[0][:2]
1773
 
                    if active_dir:
1774
 
                        active_path = active_dir + '/' + active_name
1775
 
                    else:
1776
 
                        active_path = active_name
1777
 
                    active_entry[1][1] = st('r', new_path, 0, False, '')
1778
 
                    entry[1][0] = st('r', active_path, 0, False, '')
1779
 
            elif active_kind == 'r':
1780
 
                raise NotImplementedError()
1781
 
 
1782
 
            new_kind = new_details[0]
1783
 
            if new_kind == 'd':
1784
 
                self._ensure_block(block_index, entry_index, new_path)
 
1604
            # the entry for this file_id must be in tree 0.
 
1605
            entry = self._get_entry(0, file_id, new_path)
 
1606
            if entry[0] is None or entry[0][2] != file_id:
 
1607
                self._changes_aborted = True
 
1608
                raise errors.InconsistentDelta(new_path, file_id,
 
1609
                    'working tree does not contain new entry')
 
1610
            if real_add and entry[1][1][0] not in absent:
 
1611
                self._changes_aborted = True
 
1612
                raise errors.InconsistentDelta(new_path, file_id,
 
1613
                    'The entry was considered to be a genuinely new record,'
 
1614
                    ' but there was already an old record for it.')
 
1615
            # We don't need to update the target of an 'r' because the handling
 
1616
            # of renames turns all 'r' situations into a delete at the original
 
1617
            # location.
 
1618
            entry[1][1] = new_details
1785
1619
 
1786
1620
    def _update_basis_apply_changes(self, changes):
1787
1621
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1792
1626
        absent = 'ar'
1793
1627
        for old_path, new_path, file_id, new_details in changes:
1794
1628
            # the entry for this file_id must be in tree 0.
1795
 
            entry = self._get_entry(1, file_id, new_path)
1796
 
            if entry[0] is None or entry[1][1][0] in 'ar':
1797
 
                self._raise_invalid(new_path, file_id,
1798
 
                    'changed entry considered not present')
 
1629
            entry = self._get_entry(0, file_id, new_path)
 
1630
            if entry[0] is None or entry[0][2] != file_id:
 
1631
                self._changes_aborted = True
 
1632
                raise errors.InconsistentDelta(new_path, file_id,
 
1633
                    'working tree does not contain new entry')
 
1634
            if (entry[1][0][0] in absent or
 
1635
                entry[1][1][0] in absent):
 
1636
                self._changes_aborted = True
 
1637
                raise errors.InconsistentDelta(new_path, file_id,
 
1638
                    'changed considered absent')
1799
1639
            entry[1][1] = new_details
1800
1640
 
1801
1641
    def _update_basis_apply_deletes(self, deletes):
1813
1653
        null = DirState.NULL_PARENT_DETAILS
1814
1654
        for old_path, new_path, file_id, _, real_delete in deletes:
1815
1655
            if real_delete != (new_path is None):
1816
 
                self._raise_invalid(old_path, file_id, "bad delete delta")
 
1656
                self._changes_aborted = True
 
1657
                raise AssertionError("bad delete delta")
1817
1658
            # the entry for this file_id must be in tree 1.
1818
1659
            dirname, basename = osutils.split(old_path)
1819
1660
            block_index, entry_index, dir_present, file_present = \
1820
1661
                self._get_block_entry_index(dirname, basename, 1)
1821
1662
            if not file_present:
1822
 
                self._raise_invalid(old_path, file_id,
 
1663
                self._changes_aborted = True
 
1664
                raise errors.InconsistentDelta(old_path, file_id,
1823
1665
                    'basis tree does not contain removed entry')
1824
1666
            entry = self._dirblocks[block_index][1][entry_index]
1825
 
            # The state of the entry in the 'active' WT
1826
 
            active_kind = entry[1][0][0]
1827
1667
            if entry[0][2] != file_id:
1828
 
                self._raise_invalid(old_path, file_id,
 
1668
                self._changes_aborted = True
 
1669
                raise errors.InconsistentDelta(old_path, file_id,
1829
1670
                    'mismatched file_id in tree 1')
1830
 
            dir_block = ()
1831
 
            old_kind = entry[1][1][0]
1832
 
            if active_kind in 'ar':
1833
 
                # The active tree doesn't have this file_id.
1834
 
                # The basis tree is changing this record. If this is a
1835
 
                # rename, then we don't want the record here at all
1836
 
                # anymore. If it is just an in-place change, we want the
1837
 
                # record here, but we'll add it if we need to. So we just
1838
 
                # delete it
1839
 
                if active_kind == 'r':
1840
 
                    active_path = entry[1][0][1]
1841
 
                    active_entry = self._get_entry(0, file_id, active_path)
1842
 
                    if active_entry[1][1][0] != 'r':
1843
 
                        self._raise_invalid(old_path, file_id,
1844
 
                            "Dirstate did not have matching rename entries")
1845
 
                    elif active_entry[1][0][0] in 'ar':
1846
 
                        self._raise_invalid(old_path, file_id,
1847
 
                            "Dirstate had a rename pointing at an inactive"
1848
 
                            " tree0")
1849
 
                    active_entry[1][1] = null
 
1671
            if real_delete:
 
1672
                if entry[1][0][0] != 'a':
 
1673
                    self._changes_aborted = True
 
1674
                    raise errors.InconsistentDelta(old_path, file_id,
 
1675
                            'This was marked as a real delete, but the WT state'
 
1676
                            ' claims that it still exists and is versioned.')
1850
1677
                del self._dirblocks[block_index][1][entry_index]
1851
 
                if old_kind == 'd':
1852
 
                    # This was a directory, and the active tree says it
1853
 
                    # doesn't exist, and now the basis tree says it doesn't
1854
 
                    # exist. Remove its dirblock if present
1855
 
                    (dir_block_index,
1856
 
                     present) = self._find_block_index_from_key(
1857
 
                        (old_path, '', ''))
1858
 
                    if present:
1859
 
                        dir_block = self._dirblocks[dir_block_index][1]
1860
 
                        if not dir_block:
1861
 
                            # This entry is empty, go ahead and just remove it
1862
 
                            del self._dirblocks[dir_block_index]
1863
1678
            else:
1864
 
                # There is still an active record, so just mark this
1865
 
                # removed.
1866
 
                entry[1][1] = null
1867
 
                block_i, entry_i, d_present, f_present = \
1868
 
                    self._get_block_entry_index(old_path, '', 1)
1869
 
                if d_present:
1870
 
                    dir_block = self._dirblocks[block_i][1]
1871
 
            for child_entry in dir_block:
1872
 
                child_basis_kind = child_entry[1][1][0]
1873
 
                if child_basis_kind not in 'ar':
1874
 
                    self._raise_invalid(old_path, file_id,
1875
 
                        "The file id was deleted but its children were "
1876
 
                        "not deleted.")
 
1679
                if entry[1][0][0] == 'a':
 
1680
                    self._changes_aborted = True
 
1681
                    raise errors.InconsistentDelta(old_path, file_id,
 
1682
                        'The entry was considered a rename, but the source path'
 
1683
                        ' is marked as absent.')
 
1684
                    # For whatever reason, we were asked to rename an entry
 
1685
                    # that was originally marked as deleted. This could be
 
1686
                    # because we are renaming the parent directory, and the WT
 
1687
                    # current state has the file marked as deleted.
 
1688
                elif entry[1][0][0] == 'r':
 
1689
                    # implement the rename
 
1690
                    del self._dirblocks[block_index][1][entry_index]
 
1691
                else:
 
1692
                    # it is being resurrected here, so blank it out temporarily.
 
1693
                    self._dirblocks[block_index][1][entry_index][1][1] = null
1877
1694
 
1878
1695
    def _after_delta_check_parents(self, parents, index):
1879
1696
        """Check that parents required by the delta are all intact.
1888
1705
            # has the right file id.
1889
1706
            entry = self._get_entry(index, file_id, dirname_utf8)
1890
1707
            if entry[1] is None:
1891
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1708
                self._changes_aborted = True
 
1709
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1892
1710
                    file_id, "This parent is not present.")
1893
1711
            # Parents of things must be directories
1894
1712
            if entry[1][index][0] != 'd':
1895
 
                self._raise_invalid(dirname_utf8.decode('utf8'),
 
1713
                self._changes_aborted = True
 
1714
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1896
1715
                    file_id, "This parent is not a directory.")
1897
1716
 
1898
1717
    def _observed_sha1(self, entry, sha1, stat_value,
1914
1733
                self._sha_cutoff_time()
1915
1734
            if (stat_value.st_mtime < self._cutoff_time
1916
1735
                and stat_value.st_ctime < self._cutoff_time):
1917
 
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
1918
 
                               packed_stat)
1919
 
                self._mark_modified([entry])
 
1736
                entry[1][0] = ('f', sha1, entry[1][0][2], entry[1][0][3],
 
1737
                    packed_stat)
 
1738
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1920
1739
 
1921
1740
    def _sha_cutoff_time(self):
1922
1741
        """Return cutoff time.
1980
1799
        """Serialise the entire dirstate to a sequence of lines."""
1981
1800
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1982
1801
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1983
 
            # read what's on disk.
 
1802
            # read whats on disk.
1984
1803
            self._state_file.seek(0)
1985
1804
            return self._state_file.readlines()
1986
1805
        lines = []
1987
1806
        lines.append(self._get_parents_line(self.get_parent_ids()))
1988
1807
        lines.append(self._get_ghosts_line(self._ghosts))
1989
 
        lines.extend(self._get_entry_lines())
 
1808
        # append the root line which is special cased
 
1809
        lines.extend(map(self._entry_to_line, self._iter_entries()))
1990
1810
        return self._get_output_lines(lines)
1991
1811
 
1992
1812
    def _get_ghosts_line(self, ghost_ids):
1997
1817
        """Create a line for the state file for parents information."""
1998
1818
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1999
1819
 
2000
 
    def _get_entry_lines(self):
2001
 
        """Create lines for entries."""
2002
 
        return map(self._entry_to_line, self._iter_entries())
2003
 
 
2004
1820
    def _get_fields_to_entry(self):
2005
1821
        """Get a function which converts entry fields into a entry record.
2006
1822
 
2124
1940
            entry_index += 1
2125
1941
        return block_index, entry_index, True, False
2126
1942
 
2127
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
2128
 
                   include_deleted=False):
 
1943
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
2129
1944
        """Get the dirstate entry for path in tree tree_index.
2130
1945
 
2131
1946
        If either file_id or path is supplied, it is used as the key to lookup.
2165
1980
                                          ' tree_index, file_id and path')
2166
1981
            return entry
2167
1982
        else:
2168
 
            possible_keys = self._get_id_index().get(fileid_utf8, ())
 
1983
            possible_keys = self._get_id_index().get(fileid_utf8, None)
2169
1984
            if not possible_keys:
2170
1985
                return None, None
2171
1986
            for key in possible_keys:
2273
2088
            executable = False
2274
2089
        else:
2275
2090
            raise Exception("can't pack %s" % inv_entry)
2276
 
        return static_tuple.StaticTuple(minikind, fingerprint, size,
2277
 
                                        executable, tree_data)
 
2091
        return (minikind, fingerprint, size, executable, tree_data)
2278
2092
 
2279
2093
    def _iter_child_entries(self, tree_index, path_utf8):
2280
2094
        """Iterate over all the entries that are children of path_utf.
2329
2143
                yield entry
2330
2144
 
2331
2145
    def _get_id_index(self):
2332
 
        """Get an id index of self._dirblocks.
2333
 
 
2334
 
        This maps from file_id => [(directory, name, file_id)] entries where
2335
 
        that file_id appears in one of the trees.
2336
 
        """
 
2146
        """Get an id index of self._dirblocks."""
2337
2147
        if self._id_index is None:
2338
2148
            id_index = {}
2339
2149
            for key, tree_details in self._iter_entries():
2340
 
                self._add_to_id_index(id_index, key)
 
2150
                id_index.setdefault(key[2], set()).add(key)
2341
2151
            self._id_index = id_index
2342
2152
        return self._id_index
2343
2153
 
2344
 
    def _add_to_id_index(self, id_index, entry_key):
2345
 
        """Add this entry to the _id_index mapping."""
2346
 
        # This code used to use a set for every entry in the id_index. However,
2347
 
        # it is *rare* to have more than one entry. So a set is a large
2348
 
        # overkill. And even when we do, we won't ever have more than the
2349
 
        # number of parent trees. Which is still a small number (rarely >2). As
2350
 
        # such, we use a simple tuple, and do our own uniqueness checks. While
2351
 
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
2352
 
        # cause quadratic failure.
2353
 
        file_id = entry_key[2]
2354
 
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
2355
 
        if file_id not in id_index:
2356
 
            id_index[file_id] = static_tuple.StaticTuple(entry_key,)
2357
 
        else:
2358
 
            entry_keys = id_index[file_id]
2359
 
            if entry_key not in entry_keys:
2360
 
                id_index[file_id] = entry_keys + (entry_key,)
2361
 
 
2362
 
    def _remove_from_id_index(self, id_index, entry_key):
2363
 
        """Remove this entry from the _id_index mapping.
2364
 
 
2365
 
        It is an programming error to call this when the entry_key is not
2366
 
        already present.
2367
 
        """
2368
 
        file_id = entry_key[2]
2369
 
        entry_keys = list(id_index[file_id])
2370
 
        entry_keys.remove(entry_key)
2371
 
        id_index[file_id] = static_tuple.StaticTuple.from_sequence(entry_keys)
2372
 
 
2373
2154
    def _get_output_lines(self, lines):
2374
2155
        """Format lines for final output.
2375
2156
 
2395
2176
        """The number of parent entries in each record row."""
2396
2177
        return len(self._parents) - len(self._ghosts)
2397
2178
 
2398
 
    @classmethod
2399
 
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
 
2179
    @staticmethod
 
2180
    def on_file(path, sha1_provider=None):
2400
2181
        """Construct a DirState on the file at path "path".
2401
2182
 
2402
2183
        :param path: The path at which the dirstate file on disk should live.
2403
2184
        :param sha1_provider: an object meeting the SHA1Provider interface.
2404
2185
            If None, a DefaultSHA1Provider is used.
2405
 
        :param worth_saving_limit: when the exact number of hash changed
2406
 
            entries is known, only bother saving the dirstate if more than
2407
 
            this count of entries have changed. -1 means never save.
2408
2186
        :return: An unlocked DirState object, associated with the given path.
2409
2187
        """
2410
2188
        if sha1_provider is None:
2411
2189
            sha1_provider = DefaultSHA1Provider()
2412
 
        result = cls(path, sha1_provider,
2413
 
                     worth_saving_limit=worth_saving_limit)
 
2190
        result = DirState(path, sha1_provider)
2414
2191
        return result
2415
2192
 
2416
2193
    def _read_dirblocks_if_needed(self):
2508
2285
            trace.mutter('Not saving DirState because '
2509
2286
                    '_changes_aborted is set.')
2510
2287
            return
2511
 
        # TODO: Since we now distinguish IN_MEMORY_MODIFIED from
2512
 
        #       IN_MEMORY_HASH_MODIFIED, we should only fail quietly if we fail
2513
 
        #       to save an IN_MEMORY_HASH_MODIFIED, and fail *noisily* if we
2514
 
        #       fail to save IN_MEMORY_MODIFIED
2515
 
        if not self._worth_saving():
2516
 
            return
 
2288
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
 
2289
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2517
2290
 
2518
 
        grabbed_write_lock = False
2519
 
        if self._lock_state != 'w':
2520
 
            grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
2521
 
            # Switch over to the new lock, as the old one may be closed.
2522
 
            # TODO: jam 20070315 We should validate the disk file has
2523
 
            #       not changed contents, since temporary_write_lock may
2524
 
            #       not be an atomic operation.
2525
 
            self._lock_token = new_lock
2526
 
            self._state_file = new_lock.f
2527
 
            if not grabbed_write_lock:
2528
 
                # We couldn't grab a write lock, so we switch back to a read one
2529
 
                return
2530
 
        try:
2531
 
            lines = self.get_lines()
2532
 
            self._state_file.seek(0)
2533
 
            self._state_file.writelines(lines)
2534
 
            self._state_file.truncate()
2535
 
            self._state_file.flush()
2536
 
            self._maybe_fdatasync()
2537
 
            self._mark_unmodified()
2538
 
        finally:
2539
 
            if grabbed_write_lock:
2540
 
                self._lock_token = self._lock_token.restore_read_lock()
2541
 
                self._state_file = self._lock_token.f
 
2291
            grabbed_write_lock = False
 
2292
            if self._lock_state != 'w':
 
2293
                grabbed_write_lock, new_lock = self._lock_token.temporary_write_lock()
 
2294
                # Switch over to the new lock, as the old one may be closed.
2542
2295
                # TODO: jam 20070315 We should validate the disk file has
2543
 
                #       not changed contents. Since restore_read_lock may
2544
 
                #       not be an atomic operation.                
2545
 
 
2546
 
    def _maybe_fdatasync(self):
2547
 
        """Flush to disk if possible and if not configured off."""
2548
 
        if self._config_stack.get('dirstate.fdatasync'):
2549
 
            osutils.fdatasync(self._state_file.fileno())
2550
 
 
2551
 
    def _worth_saving(self):
2552
 
        """Is it worth saving the dirstate or not?"""
2553
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED
2554
 
            or self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2555
 
            return True
2556
 
        if self._dirblock_state == DirState.IN_MEMORY_HASH_MODIFIED:
2557
 
            if self._worth_saving_limit == -1:
2558
 
                # We never save hash changes when the limit is -1
2559
 
                return False
2560
 
            # If we're using smart saving and only a small number of
2561
 
            # entries have changed their hash, don't bother saving. John has
2562
 
            # suggested using a heuristic here based on the size of the
2563
 
            # changed files and/or tree. For now, we go with a configurable
2564
 
            # number of changes, keeping the calculation time
2565
 
            # as low overhead as possible. (This also keeps all existing
2566
 
            # tests passing as the default is 0, i.e. always save.)
2567
 
            if len(self._known_hash_changes) >= self._worth_saving_limit:
2568
 
                return True
2569
 
        return False
 
2296
                #       not changed contents. Since temporary_write_lock may
 
2297
                #       not be an atomic operation.
 
2298
                self._lock_token = new_lock
 
2299
                self._state_file = new_lock.f
 
2300
                if not grabbed_write_lock:
 
2301
                    # We couldn't grab a write lock, so we switch back to a read one
 
2302
                    return
 
2303
            try:
 
2304
                self._state_file.seek(0)
 
2305
                self._state_file.writelines(self.get_lines())
 
2306
                self._state_file.truncate()
 
2307
                self._state_file.flush()
 
2308
                self._header_state = DirState.IN_MEMORY_UNMODIFIED
 
2309
                self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
 
2310
            finally:
 
2311
                if grabbed_write_lock:
 
2312
                    self._lock_token = self._lock_token.restore_read_lock()
 
2313
                    self._state_file = self._lock_token.f
 
2314
                    # TODO: jam 20070315 We should validate the disk file has
 
2315
                    #       not changed contents. Since restore_read_lock may
 
2316
                    #       not be an atomic operation.
2570
2317
 
2571
2318
    def _set_data(self, parent_ids, dirblocks):
2572
2319
        """Set the full dirstate data in memory.
2581
2328
        """
2582
2329
        # our memory copy is now authoritative.
2583
2330
        self._dirblocks = dirblocks
2584
 
        self._mark_modified(header_modified=True)
 
2331
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2332
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2585
2333
        self._parents = list(parent_ids)
2586
2334
        self._id_index = None
2587
2335
        self._packed_stat_index = None
2607
2355
        self._make_absent(entry)
2608
2356
        self.update_minimal(('', '', new_id), 'd',
2609
2357
            path_utf8='', packed_stat=entry[1][0][4])
2610
 
        self._mark_modified()
2611
 
        # XXX: This was added by Ian, we need to make sure there
2612
 
        #      are tests for it, because it isn't in bzr.dev TRUNK
2613
 
        #      It looks like the only place it is called is in setting the root
2614
 
        #      id of the tree. So probably we never had an _id_index when we
2615
 
        #      don't even have a root yet.
2616
 
        if self._id_index is not None:
2617
 
            self._add_to_id_index(self._id_index, entry[0])
 
2358
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2618
2359
 
2619
2360
    def set_parent_trees(self, trees, ghosts):
2620
2361
        """Set the parent trees for the dirstate.
2665
2406
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2666
2407
        # how many trees do we end up with
2667
2408
        parent_count = len(parent_trees)
2668
 
        st = static_tuple.StaticTuple
2669
2409
 
2670
2410
        # one: the current tree
2671
2411
        for entry in self._iter_entries():
2674
2414
                continue
2675
2415
            by_path[entry[0]] = [entry[1][0]] + \
2676
2416
                [DirState.NULL_PARENT_DETAILS] * parent_count
2677
 
            # TODO: Possibly inline this, since we know it isn't present yet
2678
 
            #       id_index[entry[0][2]] = (entry[0],)
2679
 
            self._add_to_id_index(id_index, entry[0])
 
2417
            id_index[entry[0][2]] = set([entry[0]])
2680
2418
 
2681
2419
        # now the parent trees:
2682
2420
        for tree_index, tree in enumerate(parent_trees):
2688
2426
            # the suffix is from tree_index+1:parent_count+1.
2689
2427
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2690
2428
            # now stitch in all the entries from this tree
2691
 
            last_dirname = None
2692
 
            for path, entry in tree.iter_entries_by_dir():
 
2429
            for path, entry in tree.inventory.iter_entries_by_dir():
2693
2430
                # here we process each trees details for each item in the tree.
2694
2431
                # we first update any existing entries for the id at other paths,
2695
2432
                # then we either create or update the entry for the id at the
2702
2439
                file_id = entry.file_id
2703
2440
                path_utf8 = path.encode('utf8')
2704
2441
                dirname, basename = osutils.split(path_utf8)
2705
 
                if dirname == last_dirname:
2706
 
                    # Try to re-use objects as much as possible
2707
 
                    dirname = last_dirname
2708
 
                else:
2709
 
                    last_dirname = dirname
2710
 
                new_entry_key = st(dirname, basename, file_id)
 
2442
                new_entry_key = (dirname, basename, file_id)
2711
2443
                # tree index consistency: All other paths for this id in this tree
2712
2444
                # index must point to the correct path.
2713
 
                entry_keys = id_index.get(file_id, ())
2714
 
                for entry_key in entry_keys:
 
2445
                for entry_key in id_index.setdefault(file_id, set()):
2715
2446
                    # TODO:PROFILING: It might be faster to just update
2716
2447
                    # rather than checking if we need to, and then overwrite
2717
2448
                    # the one we are located at.
2720
2451
                        # other trees, so put absent pointers there
2721
2452
                        # This is the vertical axis in the matrix, all pointing
2722
2453
                        # to the real path.
2723
 
                        by_path[entry_key][tree_index] = st('r', path_utf8, 0,
2724
 
                                                            False, '')
2725
 
                # by path consistency: Insert into an existing path record
2726
 
                # (trivial), or add a new one with relocation pointers for the
2727
 
                # other tree indexes.
2728
 
                if new_entry_key in entry_keys:
2729
 
                    # there is already an entry where this data belongs, just
2730
 
                    # insert it.
 
2454
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
 
2455
                # by path consistency: Insert into an existing path record (trivial), or
 
2456
                # add a new one with relocation pointers for the other tree indexes.
 
2457
                if new_entry_key in id_index[file_id]:
 
2458
                    # there is already an entry where this data belongs, just insert it.
2731
2459
                    by_path[new_entry_key][tree_index] = \
2732
2460
                        self._inv_entry_to_details(entry)
2733
2461
                else:
2737
2465
                    new_details = []
2738
2466
                    for lookup_index in xrange(tree_index):
2739
2467
                        # boundary case: this is the first occurence of file_id
2740
 
                        # so there are no id_indexes, possibly take this out of
 
2468
                        # so there are no id_indexs, possibly take this out of
2741
2469
                        # the loop?
2742
 
                        if not len(entry_keys):
 
2470
                        if not len(id_index[file_id]):
2743
2471
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2744
2472
                        else:
2745
2473
                            # grab any one entry, use it to find the right path.
2746
 
                            a_key = iter(entry_keys).next()
 
2474
                            # TODO: optimise this to reduce memory use in highly
 
2475
                            # fragmented situations by reusing the relocation
 
2476
                            # records.
 
2477
                            a_key = iter(id_index[file_id]).next()
2747
2478
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2748
 
                                # its a pointer or missing statement, use it as
2749
 
                                # is.
 
2479
                                # its a pointer or missing statement, use it as is.
2750
2480
                                new_details.append(by_path[a_key][lookup_index])
2751
2481
                            else:
2752
2482
                                # we have the right key, make a pointer to it.
2753
2483
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2754
 
                                new_details.append(st('r', real_path, 0, False,
2755
 
                                                      ''))
 
2484
                                new_details.append(('r', real_path, 0, False, ''))
2756
2485
                    new_details.append(self._inv_entry_to_details(entry))
2757
2486
                    new_details.extend(new_location_suffix)
2758
2487
                    by_path[new_entry_key] = new_details
2759
 
                    self._add_to_id_index(id_index, new_entry_key)
 
2488
                    id_index[file_id].add(new_entry_key)
2760
2489
        # --- end generation of full tree mappings
2761
2490
 
2762
2491
        # sort and output all the entries
2764
2493
        self._entries_to_current_state(new_entries)
2765
2494
        self._parents = [rev_id for rev_id, tree in trees]
2766
2495
        self._ghosts = list(ghosts)
2767
 
        self._mark_modified(header_modified=True)
 
2496
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
2497
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2768
2498
        self._id_index = id_index
2769
2499
 
2770
2500
    def _sort_entries(self, entry_list):
2774
2504
        try to keep everything in sorted blocks all the time, but sometimes
2775
2505
        it's easier to sort after the fact.
2776
2506
        """
2777
 
        # When sorting, we usually have 10x more entries than directories. (69k
2778
 
        # total entries, 4k directories). So cache the results of splitting.
2779
 
        # Saving time and objects. Also, use StaticTuple to avoid putting all
2780
 
        # of these object into python's garbage collector.
2781
 
        split_dirs = {}
2782
 
        def _key(entry, _split_dirs=split_dirs, _st=static_tuple.StaticTuple):
 
2507
        def _key(entry):
2783
2508
            # sort by: directory parts, file name, file id
2784
 
            dirpath, fname, file_id = entry[0]
2785
 
            try:
2786
 
                split = _split_dirs[dirpath]
2787
 
            except KeyError:
2788
 
                split = _st.from_sequence(dirpath.split('/'))
2789
 
                _split_dirs[dirpath] = split
2790
 
            return _st(split, fname, file_id)
 
2509
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
2791
2510
        return sorted(entry_list, key=_key)
2792
2511
 
2793
2512
    def set_state_from_inventory(self, new_inv):
2918
2637
                        current_old[0][1].decode('utf8'))
2919
2638
                self._make_absent(current_old)
2920
2639
                current_old = advance(old_iterator)
2921
 
        self._mark_modified()
 
2640
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2922
2641
        self._id_index = None
2923
2642
        self._packed_stat_index = None
2924
2643
        if tracing:
2925
2644
            trace.mutter("set_state_from_inventory complete.")
2926
2645
 
2927
 
    def set_state_from_scratch(self, working_inv, parent_trees, parent_ghosts):
2928
 
        """Wipe the currently stored state and set it to something new.
2929
 
 
2930
 
        This is a hard-reset for the data we are working with.
2931
 
        """
2932
 
        # Technically, we really want a write lock, but until we write, we
2933
 
        # don't really need it.
2934
 
        self._requires_lock()
2935
 
        # root dir and root dir contents with no children. We have to have a
2936
 
        # root for set_state_from_inventory to work correctly.
2937
 
        empty_root = (('', '', inventory.ROOT_ID),
2938
 
                      [('d', '', 0, False, DirState.NULLSTAT)])
2939
 
        empty_tree_dirblocks = [('', [empty_root]), ('', [])]
2940
 
        self._set_data([], empty_tree_dirblocks)
2941
 
        self.set_state_from_inventory(working_inv)
2942
 
        self.set_parent_trees(parent_trees, parent_ghosts)
2943
 
 
2944
2646
    def _make_absent(self, current_old):
2945
2647
        """Mark current_old - an entry - as absent for tree 0.
2946
2648
 
2971
2673
            block[1].pop(entry_index)
2972
2674
            # if we have an id_index in use, remove this key from it for this id.
2973
2675
            if self._id_index is not None:
2974
 
                self._remove_from_id_index(self._id_index, current_old[0])
 
2676
                self._id_index[current_old[0][2]].remove(current_old[0])
2975
2677
        # update all remaining keys for this id to record it as absent. The
2976
2678
        # existing details may either be the record we are marking as deleted
2977
2679
        # (if there were other trees with the id present at this path), or may
2990
2692
            if update_tree_details[0][0] == 'a': # absent
2991
2693
                raise AssertionError('bad row %r' % (update_tree_details,))
2992
2694
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2993
 
        self._mark_modified()
 
2695
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2994
2696
        return last_reference
2995
2697
 
2996
2698
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
3038
2740
                            # This entry has the same path (but a different id) as
3039
2741
                            # the new entry we're adding, and is present in ths
3040
2742
                            # tree.
3041
 
                            self._raise_invalid(
 
2743
                            raise errors.InconsistentDelta(
3042
2744
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
3043
2745
                                "Attempt to add item at path already occupied by "
3044
2746
                                "id %r" % entry[0][2])
3046
2748
                    else:
3047
2749
                        break
3048
2750
            # new entry, synthesis cross reference here,
3049
 
            existing_keys = id_index.get(key[2], ())
 
2751
            existing_keys = id_index.setdefault(key[2], set())
3050
2752
            if not existing_keys:
3051
2753
                # not currently in the state, simplest case
3052
2754
                new_entry = key, [new_details] + self._empty_parent_info()
3083
2785
                    # loop.
3084
2786
                    other_entry = other_block[other_entry_index]
3085
2787
                    other_entry[1][0] = ('r', path_utf8, 0, False, '')
3086
 
                    if self._maybe_remove_row(other_block, other_entry_index,
3087
 
                                              id_index):
3088
 
                        # If the row holding this was removed, we need to
3089
 
                        # recompute where this entry goes
3090
 
                        entry_index, _ = self._find_entry_index(key, block)
 
2788
                    self._maybe_remove_row(other_block, other_entry_index,
 
2789
                        id_index)
3091
2790
 
3092
2791
                # This loop:
3093
2792
                # adds a tuple to the new details for each column
3095
2794
                #  - or by creating a new pointer to the right row inside that column
3096
2795
                num_present_parents = self._num_present_parents()
3097
2796
                if num_present_parents:
3098
 
                    # TODO: This re-evaluates the existing_keys set, do we need
3099
 
                    #       to do that ourselves?
3100
2797
                    other_key = list(existing_keys)[0]
3101
2798
                for lookup_index in xrange(1, num_present_parents + 1):
3102
2799
                    # grab any one entry, use it to find the right path.
3121
2818
                        pointer_path = osutils.pathjoin(*other_key[0:2])
3122
2819
                        new_entry[1].append(('r', pointer_path, 0, False, ''))
3123
2820
            block.insert(entry_index, new_entry)
3124
 
            self._add_to_id_index(id_index, key)
 
2821
            existing_keys.add(key)
3125
2822
        else:
3126
2823
            # Does the new state matter?
3127
2824
            block[entry_index][1][0] = new_details
3136
2833
            # converted to relocated.
3137
2834
            if path_utf8 is None:
3138
2835
                raise AssertionError('no path')
3139
 
            existing_keys = id_index.get(key[2], ())
3140
 
            if key not in existing_keys:
3141
 
                raise AssertionError('We found the entry in the blocks, but'
3142
 
                    ' the key is not in the id_index.'
3143
 
                    ' key: %s, existing_keys: %s' % (key, existing_keys))
3144
 
            for entry_key in existing_keys:
 
2836
            for entry_key in id_index.setdefault(key[2], set()):
3145
2837
                # TODO:PROFILING: It might be faster to just update
3146
2838
                # rather than checking if we need to, and then overwrite
3147
2839
                # the one we are located at.
3165
2857
            if not present:
3166
2858
                self._dirblocks.insert(block_index, (subdir_key[0], []))
3167
2859
 
3168
 
        self._mark_modified()
 
2860
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
3169
2861
 
3170
2862
    def _maybe_remove_row(self, block, index, id_index):
3171
2863
        """Remove index if it is absent or relocated across the row.
3172
2864
        
3173
2865
        id_index is updated accordingly.
3174
 
        :return: True if we removed the row, False otherwise
3175
2866
        """
3176
2867
        present_in_row = False
3177
2868
        entry = block[index]
3181
2872
                break
3182
2873
        if not present_in_row:
3183
2874
            block.pop(index)
3184
 
            self._remove_from_id_index(id_index, entry[0])
3185
 
            return True
3186
 
        return False
 
2875
            id_index[entry[0][2]].remove(entry[0])
3187
2876
 
3188
2877
    def _validate(self):
3189
2878
        """Check that invariants on the dirblock are correct.
3331
3020
                        raise AssertionError(
3332
3021
                            'file_id %r did not match entry key %s'
3333
3022
                            % (file_id, entry_key))
3334
 
                if len(entry_keys) != len(set(entry_keys)):
3335
 
                    raise AssertionError(
3336
 
                        'id_index contained non-unique data for %s'
3337
 
                        % (entry_keys,))
3338
3023
 
3339
3024
    def _wipe_state(self):
3340
3025
        """Forget all state information about the dirstate."""
3437
3122
    # If we have gotten this far, that means that we need to actually
3438
3123
    # process this entry.
3439
3124
    link_or_sha1 = None
3440
 
    worth_saving = True
3441
3125
    if minikind == 'f':
3442
3126
        executable = state._is_executable(stat_value.st_mode,
3443
3127
                                         saved_executable)
3459
3143
        else:
3460
3144
            entry[1][0] = ('f', '', stat_value.st_size,
3461
3145
                           executable, DirState.NULLSTAT)
3462
 
            worth_saving = False
3463
3146
    elif minikind == 'd':
3464
3147
        link_or_sha1 = None
3465
3148
        entry[1][0] = ('d', '', 0, False, packed_stat)
3471
3154
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3472
3155
            state._ensure_block(block_index, entry_index,
3473
3156
                               osutils.pathjoin(entry[0][0], entry[0][1]))
3474
 
        else:
3475
 
            worth_saving = False
3476
3157
    elif minikind == 'l':
3477
 
        if saved_minikind == 'l':
3478
 
            worth_saving = False
3479
3158
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3480
3159
        if state._cutoff_time is None:
3481
3160
            state._sha_cutoff_time()
3486
3165
        else:
3487
3166
            entry[1][0] = ('l', '', stat_value.st_size,
3488
3167
                           False, DirState.NULLSTAT)
3489
 
    if worth_saving:
3490
 
        state._mark_modified([entry])
 
3168
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
3491
3169
    return link_or_sha1
3492
3170
 
3493
3171
 
3802
3480
            raise AssertionError("don't know how to compare "
3803
3481
                "source_minikind=%r, target_minikind=%r"
3804
3482
                % (source_minikind, target_minikind))
 
3483
            ## import pdb;pdb.set_trace()
3805
3484
        return None, None
3806
3485
 
3807
3486
    def __iter__(self):