/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Vincent Ladeuil
  • Date: 2011-10-07 14:51:42 UTC
  • mto: (6015.33.11 2.4)
  • mto: This revision was merged to the branch mainline in revision 6206.
  • Revision ID: v.ladeuil+lp@free.fr-20111007145142-oyvn7y3fhz174gs5
Here are the useful print statements used to debug the previous commit.

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