~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Martin von Gagern
  • Date: 2011-09-06 18:37:06 UTC
  • mto: This revision was merged to the branch mainline in revision 6125.
  • Revision ID: martin.vgagern@gmx.net-20110906183706-urhewu99oiqb6fer
Expose problems with multiple reconfigure requests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2006-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
20
20
lines by NL. The field delimiters are ommitted in the grammar, line delimiters
21
21
are not - this is done for clarity of reading. All string data is in utf8.
22
22
 
23
 
MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
24
 
NL = "\n";
25
 
NULL = "\0";
26
 
WHOLE_NUMBER = {digit}, digit;
27
 
BOOLEAN = "y" | "n";
28
 
REVISION_ID = a non-empty utf8 string;
29
 
 
30
 
dirstate format = header line, full checksum, row count, parent details,
31
 
 ghost_details, entries;
32
 
header line = "#bazaar dirstate flat format 3", NL;
33
 
full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
34
 
row count = "num_entries: ", WHOLE_NUMBER, NL;
35
 
parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
36
 
ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
37
 
entries = {entry};
38
 
entry = entry_key, current_entry_details, {parent_entry_details};
39
 
entry_key = dirname,  basename, fileid;
40
 
current_entry_details = common_entry_details, working_entry_details;
41
 
parent_entry_details = common_entry_details, history_entry_details;
42
 
common_entry_details = MINIKIND, fingerprint, size, executable
43
 
working_entry_details = packed_stat
44
 
history_entry_details = REVISION_ID;
45
 
executable = BOOLEAN;
46
 
size = WHOLE_NUMBER;
47
 
fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
48
 
 
49
 
Given this definition, the following is useful to know:
50
 
entry (aka row) - all the data for a given key.
51
 
entry[0]: The key (dirname, basename, fileid)
52
 
entry[0][0]: dirname
53
 
entry[0][1]: basename
54
 
entry[0][2]: fileid
55
 
entry[1]: The tree(s) data for this path and id combination.
56
 
entry[1][0]: The current tree
57
 
entry[1][1]: The second tree
58
 
 
59
 
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate:
60
 
entry[1][0][0]: minikind
61
 
entry[1][0][1]: fingerprint
62
 
entry[1][0][2]: size
63
 
entry[1][0][3]: executable
64
 
entry[1][0][4]: packed_stat
65
 
OR (for non tree-0)
66
 
entry[1][1][4]: revision_id
 
23
::
 
24
 
 
25
    MINIKIND = "f" | "d" | "l" | "a" | "r" | "t";
 
26
    NL = "\\n";
 
27
    NULL = "\\0";
 
28
    WHOLE_NUMBER = {digit}, digit;
 
29
    BOOLEAN = "y" | "n";
 
30
    REVISION_ID = a non-empty utf8 string;
 
31
    
 
32
    dirstate format = header line, full checksum, row count, parent details,
 
33
     ghost_details, entries;
 
34
    header line = "#bazaar dirstate flat format 3", NL;
 
35
    full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
 
36
    row count = "num_entries: ", WHOLE_NUMBER, NL;
 
37
    parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
 
38
    ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
 
39
    entries = {entry};
 
40
    entry = entry_key, current_entry_details, {parent_entry_details};
 
41
    entry_key = dirname,  basename, fileid;
 
42
    current_entry_details = common_entry_details, working_entry_details;
 
43
    parent_entry_details = common_entry_details, history_entry_details;
 
44
    common_entry_details = MINIKIND, fingerprint, size, executable
 
45
    working_entry_details = packed_stat
 
46
    history_entry_details = REVISION_ID;
 
47
    executable = BOOLEAN;
 
48
    size = WHOLE_NUMBER;
 
49
    fingerprint = a nonempty utf8 sequence with meaning defined by minikind.
 
50
 
 
51
Given this definition, the following is useful to know::
 
52
 
 
53
    entry (aka row) - all the data for a given key.
 
54
    entry[0]: The key (dirname, basename, fileid)
 
55
    entry[0][0]: dirname
 
56
    entry[0][1]: basename
 
57
    entry[0][2]: fileid
 
58
    entry[1]: The tree(s) data for this path and id combination.
 
59
    entry[1][0]: The current tree
 
60
    entry[1][1]: The second tree
 
61
 
 
62
For an entry for a tree, we have (using tree 0 - current tree) to demonstrate::
 
63
 
 
64
    entry[1][0][0]: minikind
 
65
    entry[1][0][1]: fingerprint
 
66
    entry[1][0][2]: size
 
67
    entry[1][0][3]: executable
 
68
    entry[1][0][4]: packed_stat
 
69
 
 
70
OR (for non tree-0)::
 
71
 
 
72
    entry[1][1][4]: revision_id
67
73
 
68
74
There may be multiple rows at the root, one per id present in the root, so the
69
 
in memory root row is now:
70
 
self._dirblocks[0] -> ('', [entry ...]),
71
 
and the entries in there are
72
 
entries[0][0]: ''
73
 
entries[0][1]: ''
74
 
entries[0][2]: file_id
75
 
entries[1][0]: The tree data for the current tree for this fileid at /
76
 
etc.
77
 
 
78
 
Kinds:
79
 
'r' is a relocated entry: This path is not present in this tree with this id,
80
 
    but the id can be found at another location. The fingerprint is used to
81
 
    point to the target location.
82
 
'a' is an absent entry: In that tree the id is not present at this path.
83
 
'd' is a directory entry: This path in this tree is a directory with the
84
 
    current file id. There is no fingerprint for directories.
85
 
'f' is a file entry: As for directory, but it's a file. The fingerprint is the
86
 
    sha1 value of the file's canonical form, i.e. after any read filters have
87
 
    been applied to the convenience form stored in the working tree.
88
 
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
89
 
    link target.
90
 
't' is a reference to a nested subtree; the fingerprint is the referenced
91
 
    revision.
 
75
in memory root row is now::
 
76
 
 
77
    self._dirblocks[0] -> ('', [entry ...]),
 
78
 
 
79
and the entries in there are::
 
80
 
 
81
    entries[0][0]: ''
 
82
    entries[0][1]: ''
 
83
    entries[0][2]: file_id
 
84
    entries[1][0]: The tree data for the current tree for this fileid at /
 
85
    etc.
 
86
 
 
87
Kinds::
 
88
 
 
89
    'r' is a relocated entry: This path is not present in this tree with this
 
90
        id, but the id can be found at another location. The fingerprint is
 
91
        used to point to the target location.
 
92
    'a' is an absent entry: In that tree the id is not present at this path.
 
93
    'd' is a directory entry: This path in this tree is a directory with the
 
94
        current file id. There is no fingerprint for directories.
 
95
    'f' is a file entry: As for directory, but it's a file. The fingerprint is
 
96
        the sha1 value of the file's canonical form, i.e. after any read
 
97
        filters have been applied to the convenience form stored in the working
 
98
        tree.
 
99
    'l' is a symlink entry: As for directory, but a symlink. The fingerprint is
 
100
        the link target.
 
101
    't' is a reference to a nested subtree; the fingerprint is the referenced
 
102
        revision.
92
103
 
93
104
Ordering:
94
105
 
95
 
The entries on disk and in memory are ordered according to the following keys:
 
106
The entries on disk and in memory are ordered according to the following keys::
96
107
 
97
108
    directory, as a list of components
98
109
    filename
99
110
    file-id
100
111
 
101
112
--- Format 1 had the following different definition: ---
102
 
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
103
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
104
 
    {PARENT ROW}
105
 
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
106
 
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
107
 
    SHA1
 
113
 
 
114
::
 
115
 
 
116
    rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
 
117
        WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
 
118
        {PARENT ROW}
 
119
    PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
 
120
        basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
 
121
        SHA1
108
122
 
109
123
PARENT ROW's are emitted for every parent that is not in the ghosts details
110
124
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
135
149
----
136
150
 
137
151
Design priorities:
138
 
 1) Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
139
 
 2) fall back current object model as needed.
140
 
 3) scale usably to the largest trees known today - say 50K entries. (mozilla
 
152
 1. Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)
 
153
 2. fall back current object model as needed.
 
154
 3. scale usably to the largest trees known today - say 50K entries. (mozilla
141
155
    is an example of this)
142
156
 
143
157
 
144
158
Locking:
 
159
 
145
160
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
146
161
 been modified, but will require that we flush/ignore cached stat-hit data
147
162
 because we won't want to restat all files on disk just because a lock was
148
163
 acquired, yet we cannot trust the data after the previous lock was released.
149
164
 
150
 
Memory representation:
 
165
Memory representation::
 
166
 
151
167
 vector of all directories, and vector of the childen ?
152
168
   i.e.
153
169
     root_entrie = (direntry for root, [parent_direntries_for_root]),
167
183
    - What's the risk of error here? Once we have the base format being processed
168
184
      we should have a net win regardless of optimality. So we are going to
169
185
      go with what seems reasonable.
 
186
 
170
187
open questions:
171
188
 
172
189
Maybe we should do a test profile of the core structure - 10K simulated
215
232
 
216
233
from bzrlib import (
217
234
    cache_utf8,
 
235
    config,
218
236
    debug,
219
237
    errors,
220
238
    inventory,
221
239
    lock,
222
240
    osutils,
 
241
    static_tuple,
223
242
    trace,
 
243
    urlutils,
224
244
    )
225
245
 
226
246
 
264
284
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
265
285
 
266
286
 
 
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
 
267
298
class SHA1Provider(object):
268
299
    """An interface for getting sha1s of a file."""
269
300
 
354
385
    NOT_IN_MEMORY = 0
355
386
    IN_MEMORY_UNMODIFIED = 1
356
387
    IN_MEMORY_MODIFIED = 2
 
388
    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates
357
389
 
358
390
    # A pack_stat (the x's) that is just noise and will never match the output
359
391
    # of base64 encode.
360
392
    NULLSTAT = 'x' * 32
361
 
    NULL_PARENT_DETAILS = ('a', '', 0, False, '')
 
393
    NULL_PARENT_DETAILS = static_tuple.StaticTuple('a', '', 0, False, '')
362
394
 
363
395
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
364
396
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
365
397
 
366
 
    def __init__(self, path, sha1_provider):
 
398
    def __init__(self, path, sha1_provider, worth_saving_limit=0):
367
399
        """Create a  DirState object.
368
400
 
369
401
        :param path: The path at which the dirstate file on disk should live.
370
402
        :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.
371
407
        """
372
408
        # _header_state and _dirblock_state represent the current state
373
409
        # of the dirstate metadata and the per-row data respectiely.
410
446
        # during commit.
411
447
        self._last_block_index = None
412
448
        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))
413
455
 
414
456
    def __repr__(self):
415
457
        return "%s(%r)" % \
416
458
            (self.__class__.__name__, self._filename)
417
459
 
 
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
 
418
491
    def add(self, path, file_id, kind, stat, fingerprint):
419
492
        """Add a path to be tracked.
420
493
 
546
619
        if kind == 'directory':
547
620
           # insert a new dirblock
548
621
           self._ensure_block(block_index, entry_index, utf8path)
549
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
622
        self._mark_modified()
550
623
        if self._id_index:
551
 
            self._id_index.setdefault(entry_key[2], set()).add(entry_key)
 
624
            self._add_to_id_index(self._id_index, entry_key)
552
625
 
553
626
    def _bisect(self, paths):
554
627
        """Bisect through the disk structure for specific rows.
1018
1091
 
1019
1092
        self._ghosts = []
1020
1093
        self._parents = [parents[0]]
1021
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1022
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1094
        self._mark_modified(header_modified=True)
1023
1095
 
1024
1096
    def _empty_parent_info(self):
1025
1097
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1154
1226
    def _fields_per_entry(self):
1155
1227
        """How many null separated fields should be in each entry row.
1156
1228
 
1157
 
        Each line now has an extra '\n' field which is not used
 
1229
        Each line now has an extra '\\n' field which is not used
1158
1230
        so we just skip over it
1159
 
        entry size:
 
1231
 
 
1232
        entry size::
1160
1233
            3 fields for the key
1161
1234
            + number of fields per tree_data (5) * tree count
1162
1235
            + newline
1275
1348
            raise
1276
1349
        return result
1277
1350
 
 
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
 
1278
1359
    def update_by_delta(self, delta):
1279
1360
        """Apply an inventory delta to the dirstate for tree 0
1280
1361
 
1298
1379
        new_ids = set()
1299
1380
        # This loop transforms the delta to single atomic operations that can
1300
1381
        # be executed and validated.
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):
 
1382
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
 
1383
        for old_path, new_path, file_id, inv_entry in delta:
1308
1384
            if (file_id in insertions) or (file_id in removals):
1309
 
                raise errors.InconsistentDelta(old_path or new_path, file_id,
 
1385
                self._raise_invalid(old_path or new_path, file_id,
1310
1386
                    "repeated file_id")
1311
1387
            if old_path is not None:
1312
1388
                old_path = old_path.encode('utf-8')
1315
1391
                new_ids.add(file_id)
1316
1392
            if new_path is not None:
1317
1393
                if inv_entry is None:
1318
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1394
                    self._raise_invalid(new_path, file_id,
1319
1395
                        "new_path with no entry")
1320
1396
                new_path = new_path.encode('utf-8')
1321
1397
                dirname_utf8, basename = osutils.split(new_path)
1362
1438
            # _get_entry raises BzrError when a request is inconsistent; we
1363
1439
            # want such errors to be shown as InconsistentDelta - and that 
1364
1440
            # fits the behaviour we trigger.
1365
 
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1441
            raise errors.InconsistentDeltaDelta(delta,
 
1442
                "error from _get_entry. %s" % (e,))
1366
1443
 
1367
1444
    def _apply_removals(self, removals):
1368
1445
        for file_id, path in sorted(removals, reverse=True,
1373
1450
            try:
1374
1451
                entry = self._dirblocks[block_i][1][entry_i]
1375
1452
            except IndexError:
1376
 
                self._changes_aborted = True
1377
 
                raise errors.InconsistentDelta(path, file_id,
 
1453
                self._raise_invalid(path, file_id,
1378
1454
                    "Wrong path for old path.")
1379
1455
            if not f_present or entry[1][0][0] in 'ar':
1380
 
                self._changes_aborted = True
1381
 
                raise errors.InconsistentDelta(path, file_id,
 
1456
                self._raise_invalid(path, file_id,
1382
1457
                    "Wrong path for old path.")
1383
1458
            if file_id != entry[0][2]:
1384
 
                self._changes_aborted = True
1385
 
                raise errors.InconsistentDelta(path, file_id,
 
1459
                self._raise_invalid(path, file_id,
1386
1460
                    "Attempt to remove path has wrong id - found %r."
1387
1461
                    % entry[0][2])
1388
1462
            self._make_absent(entry)
1398
1472
                # be due to it being in a parent tree, or a corrupt delta.
1399
1473
                for child_entry in self._dirblocks[block_i][1]:
1400
1474
                    if child_entry[1][0][0] not in ('r', 'a'):
1401
 
                        self._changes_aborted = True
1402
 
                        raise errors.InconsistentDelta(path, entry[0][2],
 
1475
                        self._raise_invalid(path, entry[0][2],
1403
1476
                            "The file id was deleted but its children were "
1404
1477
                            "not deleted.")
1405
1478
 
1409
1482
                self.update_minimal(key, minikind, executable, fingerprint,
1410
1483
                                    path_utf8=path_utf8)
1411
1484
        except errors.NotVersionedError:
1412
 
            self._changes_aborted = True
1413
 
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
 
1485
            self._raise_invalid(path_utf8.decode('utf8'), key[2],
1414
1486
                "Missing parent")
1415
1487
 
1416
1488
    def update_basis_by_delta(self, delta, new_revid):
1424
1496
        Note that an exception during the operation of this method will leave
1425
1497
        the dirstate in a corrupt state where it should not be saved.
1426
1498
 
1427
 
        Finally, we expect all changes to be synchronising the basis tree with
1428
 
        the working tree.
1429
 
 
1430
1499
        :param new_revid: The new revision id for the trees parent.
1431
1500
        :param delta: An inventory delta (see apply_inventory_delta) describing
1432
1501
            the changes from the current left most parent revision to new_revid.
1444
1513
 
1445
1514
        self._parents[0] = new_revid
1446
1515
 
1447
 
        delta = sorted(delta, reverse=True)
 
1516
        delta = sorted(self._check_delta_is_valid(delta), reverse=True)
1448
1517
        adds = []
1449
1518
        changes = []
1450
1519
        deletes = []
1471
1540
        new_ids = set()
1472
1541
        for old_path, new_path, file_id, inv_entry in delta:
1473
1542
            if inv_entry is not None and file_id != inv_entry.file_id:
1474
 
                raise errors.InconsistentDelta(new_path, file_id,
 
1543
                self._raise_invalid(new_path, file_id,
1475
1544
                    "mismatched entry file_id %r" % inv_entry)
1476
 
            if new_path is not None:
 
1545
            if new_path is None:
 
1546
                new_path_utf8 = None
 
1547
            else:
1477
1548
                if inv_entry is None:
1478
 
                    raise errors.InconsistentDelta(new_path, file_id,
 
1549
                    self._raise_invalid(new_path, file_id,
1479
1550
                        "new_path with no entry")
1480
1551
                new_path_utf8 = encode(new_path)
1481
1552
                # note the parent for validation
1483
1554
                if basename_utf8:
1484
1555
                    parents.add((dirname_utf8, inv_entry.parent_id))
1485
1556
            if old_path is None:
1486
 
                adds.append((None, encode(new_path), file_id,
 
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,
1487
1562
                    inv_to_entry(inv_entry), True))
1488
1563
                new_ids.add(file_id)
1489
1564
            elif new_path is None:
1490
 
                deletes.append((encode(old_path), None, file_id, None, True))
1491
 
            elif (old_path, new_path) != root_only:
 
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:
1492
1578
                # Renames:
1493
1579
                # Because renames must preserve their children we must have
1494
1580
                # processed all relocations and removes before hand. The sort
1504
1590
                self._update_basis_apply_deletes(deletes)
1505
1591
                deletes = []
1506
1592
                # Split into an add/delete pair recursively.
1507
 
                adds.append((None, new_path_utf8, file_id,
1508
 
                    inv_to_entry(inv_entry), False))
 
1593
                adds.append((old_path_utf8, new_path_utf8, file_id,
 
1594
                             inv_to_entry(inv_entry), False))
1509
1595
                # Expunge deletes that we've seen so that deleted/renamed
1510
1596
                # children of a rename directory are handled correctly.
1511
 
                new_deletes = reversed(list(self._iter_child_entries(1,
1512
 
                    encode(old_path))))
 
1597
                new_deletes = reversed(list(
 
1598
                    self._iter_child_entries(1, old_path_utf8)))
1513
1599
                # Remove the current contents of the tree at orig_path, and
1514
1600
                # reinsert at the correct new path.
1515
1601
                for entry in new_deletes:
1516
 
                    if entry[0][0]:
1517
 
                        source_path = entry[0][0] + '/' + entry[0][1]
 
1602
                    child_dirname, child_basename, child_file_id = entry[0]
 
1603
                    if child_dirname:
 
1604
                        source_path = child_dirname + '/' + child_basename
1518
1605
                    else:
1519
 
                        source_path = entry[0][1]
 
1606
                        source_path = child_basename
1520
1607
                    if new_path_utf8:
1521
1608
                        target_path = new_path_utf8 + source_path[len(old_path):]
1522
1609
                    else:
1523
1610
                        if old_path == '':
1524
1611
                            raise AssertionError("cannot rename directory to"
1525
 
                                " itself")
 
1612
                                                 " itself")
1526
1613
                        target_path = source_path[len(old_path) + 1:]
1527
1614
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
1528
1615
                    deletes.append(
1529
1616
                        (source_path, target_path, entry[0][2], 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)))
 
1617
                deletes.append((old_path_utf8, new_path, file_id, None, False))
1537
1618
        self._check_delta_ids_absent(new_ids, delta, 1)
1538
1619
        try:
1539
1620
            # Finish expunging deletes/first half of renames.
1549
1630
            if 'integrity error' not in str(e):
1550
1631
                raise
1551
1632
            # _get_entry raises BzrError when a request is inconsistent; we
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.")
 
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,))
1557
1637
 
1558
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1559
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1638
        self._mark_modified(header_modified=True)
1560
1639
        self._id_index = None
1561
1640
        return
1562
1641
 
1566
1645
            return
1567
1646
        id_index = self._get_id_index()
1568
1647
        for file_id in new_ids:
1569
 
            for key in id_index.get(file_id, []):
 
1648
            for key in id_index.get(file_id, ()):
1570
1649
                block_i, entry_i, d_present, f_present = \
1571
1650
                    self._get_block_entry_index(key[0], key[1], tree_index)
1572
1651
                if not f_present:
1576
1655
                if entry[0][2] != file_id:
1577
1656
                    # Different file_id, so not what we want.
1578
1657
                    continue
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,
 
1658
                self._raise_invalid(("%s/%s" % key[0:2]).decode('utf8'), file_id,
1583
1659
                    "This file_id is new in the delta but already present in "
1584
1660
                    "the target")
1585
1661
 
 
1662
    def _raise_invalid(self, path, file_id, reason):
 
1663
        self._changes_aborted = True
 
1664
        raise errors.InconsistentDelta(path, file_id, reason)
 
1665
 
1586
1666
    def _update_basis_apply_adds(self, adds):
1587
1667
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1588
1668
 
1596
1676
        """
1597
1677
        # Adds are accumulated partly from renames, so can be in any input
1598
1678
        # order - sort it.
1599
 
        adds.sort()
 
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])
1600
1683
        # adds is now in lexographic order, which places all parents before
1601
1684
        # their children, so we can process it linearly.
1602
1685
        absent = 'ar'
 
1686
        st = static_tuple.StaticTuple
1603
1687
        for old_path, new_path, file_id, new_details, real_add in adds:
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
 
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)
1619
1785
 
1620
1786
    def _update_basis_apply_changes(self, changes):
1621
1787
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
1626
1792
        absent = 'ar'
1627
1793
        for old_path, new_path, file_id, new_details in changes:
1628
1794
            # the entry for this file_id must be in tree 0.
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')
 
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')
1639
1799
            entry[1][1] = new_details
1640
1800
 
1641
1801
    def _update_basis_apply_deletes(self, deletes):
1653
1813
        null = DirState.NULL_PARENT_DETAILS
1654
1814
        for old_path, new_path, file_id, _, real_delete in deletes:
1655
1815
            if real_delete != (new_path is None):
1656
 
                self._changes_aborted = True
1657
 
                raise AssertionError("bad delete delta")
 
1816
                self._raise_invalid(old_path, file_id, "bad delete delta")
1658
1817
            # the entry for this file_id must be in tree 1.
1659
1818
            dirname, basename = osutils.split(old_path)
1660
1819
            block_index, entry_index, dir_present, file_present = \
1661
1820
                self._get_block_entry_index(dirname, basename, 1)
1662
1821
            if not file_present:
1663
 
                self._changes_aborted = True
1664
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1822
                self._raise_invalid(old_path, file_id,
1665
1823
                    'basis tree does not contain removed entry')
1666
1824
            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]
1667
1827
            if entry[0][2] != file_id:
1668
 
                self._changes_aborted = True
1669
 
                raise errors.InconsistentDelta(old_path, file_id,
 
1828
                self._raise_invalid(old_path, file_id,
1670
1829
                    'mismatched file_id in tree 1')
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.')
 
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
1677
1850
                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]
1678
1863
            else:
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
 
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.")
1694
1877
 
1695
1878
    def _after_delta_check_parents(self, parents, index):
1696
1879
        """Check that parents required by the delta are all intact.
1705
1888
            # has the right file id.
1706
1889
            entry = self._get_entry(index, file_id, dirname_utf8)
1707
1890
            if entry[1] is None:
1708
 
                self._changes_aborted = True
1709
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1891
                self._raise_invalid(dirname_utf8.decode('utf8'),
1710
1892
                    file_id, "This parent is not present.")
1711
1893
            # Parents of things must be directories
1712
1894
            if entry[1][index][0] != 'd':
1713
 
                self._changes_aborted = True
1714
 
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1895
                self._raise_invalid(dirname_utf8.decode('utf8'),
1715
1896
                    file_id, "This parent is not a directory.")
1716
1897
 
1717
1898
    def _observed_sha1(self, entry, sha1, stat_value,
1733
1914
                self._sha_cutoff_time()
1734
1915
            if (stat_value.st_mtime < self._cutoff_time
1735
1916
                and stat_value.st_ctime < self._cutoff_time):
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
 
1917
                entry[1][0] = ('f', sha1, stat_value.st_size, entry[1][0][3],
 
1918
                               packed_stat)
 
1919
                self._mark_modified([entry])
1739
1920
 
1740
1921
    def _sha_cutoff_time(self):
1741
1922
        """Return cutoff time.
1799
1980
        """Serialise the entire dirstate to a sequence of lines."""
1800
1981
        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
1801
1982
            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
1802
 
            # read whats on disk.
 
1983
            # read what's on disk.
1803
1984
            self._state_file.seek(0)
1804
1985
            return self._state_file.readlines()
1805
1986
        lines = []
1806
1987
        lines.append(self._get_parents_line(self.get_parent_ids()))
1807
1988
        lines.append(self._get_ghosts_line(self._ghosts))
1808
 
        # append the root line which is special cased
1809
 
        lines.extend(map(self._entry_to_line, self._iter_entries()))
 
1989
        lines.extend(self._get_entry_lines())
1810
1990
        return self._get_output_lines(lines)
1811
1991
 
1812
1992
    def _get_ghosts_line(self, ghost_ids):
1817
1997
        """Create a line for the state file for parents information."""
1818
1998
        return '\0'.join([str(len(parent_ids))] + parent_ids)
1819
1999
 
 
2000
    def _get_entry_lines(self):
 
2001
        """Create lines for entries."""
 
2002
        return map(self._entry_to_line, self._iter_entries())
 
2003
 
1820
2004
    def _get_fields_to_entry(self):
1821
2005
        """Get a function which converts entry fields into a entry record.
1822
2006
 
1940
2124
            entry_index += 1
1941
2125
        return block_index, entry_index, True, False
1942
2126
 
1943
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
2127
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None,
 
2128
                   include_deleted=False):
1944
2129
        """Get the dirstate entry for path in tree tree_index.
1945
2130
 
1946
2131
        If either file_id or path is supplied, it is used as the key to lookup.
1980
2165
                                          ' tree_index, file_id and path')
1981
2166
            return entry
1982
2167
        else:
1983
 
            possible_keys = self._get_id_index().get(fileid_utf8, None)
 
2168
            possible_keys = self._get_id_index().get(fileid_utf8, ())
1984
2169
            if not possible_keys:
1985
2170
                return None, None
1986
2171
            for key in possible_keys:
2088
2273
            executable = False
2089
2274
        else:
2090
2275
            raise Exception("can't pack %s" % inv_entry)
2091
 
        return (minikind, fingerprint, size, executable, tree_data)
 
2276
        return static_tuple.StaticTuple(minikind, fingerprint, size,
 
2277
                                        executable, tree_data)
2092
2278
 
2093
2279
    def _iter_child_entries(self, tree_index, path_utf8):
2094
2280
        """Iterate over all the entries that are children of path_utf.
2143
2329
                yield entry
2144
2330
 
2145
2331
    def _get_id_index(self):
2146
 
        """Get an id index of self._dirblocks."""
 
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
        """
2147
2337
        if self._id_index is None:
2148
2338
            id_index = {}
2149
2339
            for key, tree_details in self._iter_entries():
2150
 
                id_index.setdefault(key[2], set()).add(key)
 
2340
                self._add_to_id_index(id_index, key)
2151
2341
            self._id_index = id_index
2152
2342
        return self._id_index
2153
2343
 
 
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
 
2154
2373
    def _get_output_lines(self, lines):
2155
2374
        """Format lines for final output.
2156
2375
 
2176
2395
        """The number of parent entries in each record row."""
2177
2396
        return len(self._parents) - len(self._ghosts)
2178
2397
 
2179
 
    @staticmethod
2180
 
    def on_file(path, sha1_provider=None):
 
2398
    @classmethod
 
2399
    def on_file(cls, path, sha1_provider=None, worth_saving_limit=0):
2181
2400
        """Construct a DirState on the file at path "path".
2182
2401
 
2183
2402
        :param path: The path at which the dirstate file on disk should live.
2184
2403
        :param sha1_provider: an object meeting the SHA1Provider interface.
2185
2404
            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.
2186
2408
        :return: An unlocked DirState object, associated with the given path.
2187
2409
        """
2188
2410
        if sha1_provider is None:
2189
2411
            sha1_provider = DefaultSHA1Provider()
2190
 
        result = DirState(path, sha1_provider)
 
2412
        result = cls(path, sha1_provider,
 
2413
                     worth_saving_limit=worth_saving_limit)
2191
2414
        return result
2192
2415
 
2193
2416
    def _read_dirblocks_if_needed(self):
2285
2508
            trace.mutter('Not saving DirState because '
2286
2509
                    '_changes_aborted is set.')
2287
2510
            return
2288
 
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2289
 
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
 
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
2290
2517
 
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.
 
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
2295
2542
                # TODO: jam 20070315 We should validate the disk file has
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.
 
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
2317
2570
 
2318
2571
    def _set_data(self, parent_ids, dirblocks):
2319
2572
        """Set the full dirstate data in memory.
2328
2581
        """
2329
2582
        # our memory copy is now authoritative.
2330
2583
        self._dirblocks = dirblocks
2331
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2332
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2584
        self._mark_modified(header_modified=True)
2333
2585
        self._parents = list(parent_ids)
2334
2586
        self._id_index = None
2335
2587
        self._packed_stat_index = None
2355
2607
        self._make_absent(entry)
2356
2608
        self.update_minimal(('', '', new_id), 'd',
2357
2609
            path_utf8='', packed_stat=entry[1][0][4])
2358
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
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])
2359
2618
 
2360
2619
    def set_parent_trees(self, trees, ghosts):
2361
2620
        """Set the parent trees for the dirstate.
2406
2665
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2407
2666
        # how many trees do we end up with
2408
2667
        parent_count = len(parent_trees)
 
2668
        st = static_tuple.StaticTuple
2409
2669
 
2410
2670
        # one: the current tree
2411
2671
        for entry in self._iter_entries():
2414
2674
                continue
2415
2675
            by_path[entry[0]] = [entry[1][0]] + \
2416
2676
                [DirState.NULL_PARENT_DETAILS] * parent_count
2417
 
            id_index[entry[0][2]] = set([entry[0]])
 
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])
2418
2680
 
2419
2681
        # now the parent trees:
2420
2682
        for tree_index, tree in enumerate(parent_trees):
2426
2688
            # the suffix is from tree_index+1:parent_count+1.
2427
2689
            new_location_suffix = [DirState.NULL_PARENT_DETAILS] * (parent_count - tree_index)
2428
2690
            # now stitch in all the entries from this tree
2429
 
            for path, entry in tree.inventory.iter_entries_by_dir():
 
2691
            last_dirname = None
 
2692
            for path, entry in tree.iter_entries_by_dir():
2430
2693
                # here we process each trees details for each item in the tree.
2431
2694
                # we first update any existing entries for the id at other paths,
2432
2695
                # then we either create or update the entry for the id at the
2439
2702
                file_id = entry.file_id
2440
2703
                path_utf8 = path.encode('utf8')
2441
2704
                dirname, basename = osutils.split(path_utf8)
2442
 
                new_entry_key = (dirname, basename, file_id)
 
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)
2443
2711
                # tree index consistency: All other paths for this id in this tree
2444
2712
                # index must point to the correct path.
2445
 
                for entry_key in id_index.setdefault(file_id, set()):
 
2713
                entry_keys = id_index.get(file_id, ())
 
2714
                for entry_key in entry_keys:
2446
2715
                    # TODO:PROFILING: It might be faster to just update
2447
2716
                    # rather than checking if we need to, and then overwrite
2448
2717
                    # the one we are located at.
2451
2720
                        # other trees, so put absent pointers there
2452
2721
                        # This is the vertical axis in the matrix, all pointing
2453
2722
                        # to the real path.
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.
 
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.
2459
2731
                    by_path[new_entry_key][tree_index] = \
2460
2732
                        self._inv_entry_to_details(entry)
2461
2733
                else:
2465
2737
                    new_details = []
2466
2738
                    for lookup_index in xrange(tree_index):
2467
2739
                        # boundary case: this is the first occurence of file_id
2468
 
                        # so there are no id_indexs, possibly take this out of
 
2740
                        # so there are no id_indexes, possibly take this out of
2469
2741
                        # the loop?
2470
 
                        if not len(id_index[file_id]):
 
2742
                        if not len(entry_keys):
2471
2743
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2472
2744
                        else:
2473
2745
                            # grab any one entry, use it to find the right path.
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()
 
2746
                            a_key = iter(entry_keys).next()
2478
2747
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2479
 
                                # its a pointer or missing statement, use it as is.
 
2748
                                # its a pointer or missing statement, use it as
 
2749
                                # is.
2480
2750
                                new_details.append(by_path[a_key][lookup_index])
2481
2751
                            else:
2482
2752
                                # we have the right key, make a pointer to it.
2483
2753
                                real_path = ('/'.join(a_key[0:2])).strip('/')
2484
 
                                new_details.append(('r', real_path, 0, False, ''))
 
2754
                                new_details.append(st('r', real_path, 0, False,
 
2755
                                                      ''))
2485
2756
                    new_details.append(self._inv_entry_to_details(entry))
2486
2757
                    new_details.extend(new_location_suffix)
2487
2758
                    by_path[new_entry_key] = new_details
2488
 
                    id_index[file_id].add(new_entry_key)
 
2759
                    self._add_to_id_index(id_index, new_entry_key)
2489
2760
        # --- end generation of full tree mappings
2490
2761
 
2491
2762
        # sort and output all the entries
2493
2764
        self._entries_to_current_state(new_entries)
2494
2765
        self._parents = [rev_id for rev_id, tree in trees]
2495
2766
        self._ghosts = list(ghosts)
2496
 
        self._header_state = DirState.IN_MEMORY_MODIFIED
2497
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2767
        self._mark_modified(header_modified=True)
2498
2768
        self._id_index = id_index
2499
2769
 
2500
2770
    def _sort_entries(self, entry_list):
2504
2774
        try to keep everything in sorted blocks all the time, but sometimes
2505
2775
        it's easier to sort after the fact.
2506
2776
        """
2507
 
        def _key(entry):
 
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):
2508
2783
            # sort by: directory parts, file name, file id
2509
 
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
 
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)
2510
2791
        return sorted(entry_list, key=_key)
2511
2792
 
2512
2793
    def set_state_from_inventory(self, new_inv):
2637
2918
                        current_old[0][1].decode('utf8'))
2638
2919
                self._make_absent(current_old)
2639
2920
                current_old = advance(old_iterator)
2640
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2921
        self._mark_modified()
2641
2922
        self._id_index = None
2642
2923
        self._packed_stat_index = None
2643
2924
        if tracing:
2644
2925
            trace.mutter("set_state_from_inventory complete.")
2645
2926
 
 
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
 
2646
2944
    def _make_absent(self, current_old):
2647
2945
        """Mark current_old - an entry - as absent for tree 0.
2648
2946
 
2673
2971
            block[1].pop(entry_index)
2674
2972
            # if we have an id_index in use, remove this key from it for this id.
2675
2973
            if self._id_index is not None:
2676
 
                self._id_index[current_old[0][2]].remove(current_old[0])
 
2974
                self._remove_from_id_index(self._id_index, current_old[0])
2677
2975
        # update all remaining keys for this id to record it as absent. The
2678
2976
        # existing details may either be the record we are marking as deleted
2679
2977
        # (if there were other trees with the id present at this path), or may
2692
2990
            if update_tree_details[0][0] == 'a': # absent
2693
2991
                raise AssertionError('bad row %r' % (update_tree_details,))
2694
2992
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2695
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
2993
        self._mark_modified()
2696
2994
        return last_reference
2697
2995
 
2698
2996
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2740
3038
                            # This entry has the same path (but a different id) as
2741
3039
                            # the new entry we're adding, and is present in ths
2742
3040
                            # tree.
2743
 
                            raise errors.InconsistentDelta(
 
3041
                            self._raise_invalid(
2744
3042
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
2745
3043
                                "Attempt to add item at path already occupied by "
2746
3044
                                "id %r" % entry[0][2])
2748
3046
                    else:
2749
3047
                        break
2750
3048
            # new entry, synthesis cross reference here,
2751
 
            existing_keys = id_index.setdefault(key[2], set())
 
3049
            existing_keys = id_index.get(key[2], ())
2752
3050
            if not existing_keys:
2753
3051
                # not currently in the state, simplest case
2754
3052
                new_entry = key, [new_details] + self._empty_parent_info()
2785
3083
                    # loop.
2786
3084
                    other_entry = other_block[other_entry_index]
2787
3085
                    other_entry[1][0] = ('r', path_utf8, 0, False, '')
2788
 
                    self._maybe_remove_row(other_block, other_entry_index,
2789
 
                        id_index)
 
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)
2790
3091
 
2791
3092
                # This loop:
2792
3093
                # adds a tuple to the new details for each column
2794
3095
                #  - or by creating a new pointer to the right row inside that column
2795
3096
                num_present_parents = self._num_present_parents()
2796
3097
                if num_present_parents:
 
3098
                    # TODO: This re-evaluates the existing_keys set, do we need
 
3099
                    #       to do that ourselves?
2797
3100
                    other_key = list(existing_keys)[0]
2798
3101
                for lookup_index in xrange(1, num_present_parents + 1):
2799
3102
                    # grab any one entry, use it to find the right path.
2818
3121
                        pointer_path = osutils.pathjoin(*other_key[0:2])
2819
3122
                        new_entry[1].append(('r', pointer_path, 0, False, ''))
2820
3123
            block.insert(entry_index, new_entry)
2821
 
            existing_keys.add(key)
 
3124
            self._add_to_id_index(id_index, key)
2822
3125
        else:
2823
3126
            # Does the new state matter?
2824
3127
            block[entry_index][1][0] = new_details
2833
3136
            # converted to relocated.
2834
3137
            if path_utf8 is None:
2835
3138
                raise AssertionError('no path')
2836
 
            for entry_key in id_index.setdefault(key[2], set()):
 
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:
2837
3145
                # TODO:PROFILING: It might be faster to just update
2838
3146
                # rather than checking if we need to, and then overwrite
2839
3147
                # the one we are located at.
2857
3165
            if not present:
2858
3166
                self._dirblocks.insert(block_index, (subdir_key[0], []))
2859
3167
 
2860
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3168
        self._mark_modified()
2861
3169
 
2862
3170
    def _maybe_remove_row(self, block, index, id_index):
2863
3171
        """Remove index if it is absent or relocated across the row.
2864
3172
        
2865
3173
        id_index is updated accordingly.
 
3174
        :return: True if we removed the row, False otherwise
2866
3175
        """
2867
3176
        present_in_row = False
2868
3177
        entry = block[index]
2872
3181
                break
2873
3182
        if not present_in_row:
2874
3183
            block.pop(index)
2875
 
            id_index[entry[0][2]].remove(entry[0])
 
3184
            self._remove_from_id_index(id_index, entry[0])
 
3185
            return True
 
3186
        return False
2876
3187
 
2877
3188
    def _validate(self):
2878
3189
        """Check that invariants on the dirblock are correct.
3020
3331
                        raise AssertionError(
3021
3332
                            'file_id %r did not match entry key %s'
3022
3333
                            % (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,))
3023
3338
 
3024
3339
    def _wipe_state(self):
3025
3340
        """Forget all state information about the dirstate."""
3122
3437
    # If we have gotten this far, that means that we need to actually
3123
3438
    # process this entry.
3124
3439
    link_or_sha1 = None
 
3440
    worth_saving = True
3125
3441
    if minikind == 'f':
3126
3442
        executable = state._is_executable(stat_value.st_mode,
3127
3443
                                         saved_executable)
3143
3459
        else:
3144
3460
            entry[1][0] = ('f', '', stat_value.st_size,
3145
3461
                           executable, DirState.NULLSTAT)
 
3462
            worth_saving = False
3146
3463
    elif minikind == 'd':
3147
3464
        link_or_sha1 = None
3148
3465
        entry[1][0] = ('d', '', 0, False, packed_stat)
3154
3471
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
3155
3472
            state._ensure_block(block_index, entry_index,
3156
3473
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
3474
        else:
 
3475
            worth_saving = False
3157
3476
    elif minikind == 'l':
 
3477
        if saved_minikind == 'l':
 
3478
            worth_saving = False
3158
3479
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
3159
3480
        if state._cutoff_time is None:
3160
3481
            state._sha_cutoff_time()
3165
3486
        else:
3166
3487
            entry[1][0] = ('l', '', stat_value.st_size,
3167
3488
                           False, DirState.NULLSTAT)
3168
 
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3489
    if worth_saving:
 
3490
        state._mark_modified([entry])
3169
3491
    return link_or_sha1
3170
3492
 
3171
3493
 
3480
3802
            raise AssertionError("don't know how to compare "
3481
3803
                "source_minikind=%r, target_minikind=%r"
3482
3804
                % (source_minikind, target_minikind))
3483
 
            ## import pdb;pdb.set_trace()
3484
3805
        return None, None
3485
3806
 
3486
3807
    def __iter__(self):