← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Robert Collins
  • Date: 2007-10-23 22:14:32 UTC
  • mto: (2592.6.3 repository)
  • mto: This revision was merged to the branch mainline in revision 2967.
  • Revision ID: robertc@robertcollins.net-20071023221432-j8zndh1oiegql3cu
* Commit updates the state of the working tree via a delta rather than
  supplying entirely new basis trees. For commit of a single specified file
  this reduces the wall clock time for commit by roughly a 30%.
  (Robert Collins, Martin Pool)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/dirstate.py
212
212
import zlib
213
213
 
214
214
from bzrlib import (
 
215
    cache_utf8,
215
216
    debug,
216
217
    errors,
217
218
    inventory,
305
306
    def __init__(self, path):
306
307
        """Create a  DirState object.
307
308
 
308
 
        Attributes of note:
309
 
 
310
 
        :attr _root_entrie: The root row of the directory/file information,
311
 
            - contains the path to / - '', ''
312
 
            - kind of 'directory',
313
 
            - the file id of the root in utf8
314
 
            - size of 0
315
 
            - a packed state
316
 
            - and no sha information.
317
309
        :param path: The path at which the dirstate file on disk should live.
318
310
        """
319
311
        # _header_state and _dirblock_state represent the current state
897
889
            processed_dirs.update(pending_dirs)
898
890
        return found
899
891
 
 
892
    def _discard_merge_parents(self):
 
893
        """Discard any parents trees beyond the first.
 
894
        
 
895
        Note that if this fails the dirstate is corrupted.
 
896
 
 
897
        After this function returns the dirstate contains 2 trees, neither of
 
898
        which are ghosted.
 
899
        """
 
900
        self._read_header_if_needed()
 
901
        parents = self.get_parent_ids()
 
902
        if len(parents) < 1:
 
903
            return
 
904
        # only require all dirblocks if we are doing a full-pass removal.
 
905
        self._read_dirblocks_if_needed()
 
906
        dead_patterns = set([('a', 'r'), ('a', 'a'), ('r', 'r'), ('r', 'a')])
 
907
        def iter_entries_removable():
 
908
            for block in self._dirblocks:
 
909
                deleted_positions = []
 
910
                for pos, entry in enumerate(block[1]):
 
911
                    yield entry
 
912
                    if (entry[1][0][0], entry[1][1][0]) in dead_patterns:
 
913
                        deleted_positions.append(pos)
 
914
                if deleted_positions:
 
915
                    if len(deleted_positions) == len(block):
 
916
                        del block[1][:]
 
917
                    else:
 
918
                        for pos in reversed(deleted_positions):
 
919
                            del block[1][pos]
 
920
        # if the first parent is a ghost:
 
921
        if parents[0] in self.get_ghosts():
 
922
            empty_parent = [DirState.NULL_PARENT_DETAILS]
 
923
            for entry in iter_entries_removable():
 
924
                entry[1][1:] = empty_parent
 
925
        else:
 
926
            for entry in iter_entries_removable():
 
927
                del entry[1][2:]
 
928
 
 
929
        self._ghosts = []
 
930
        self._parents = [parents[0]]
 
931
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
932
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
933
 
900
934
    def _empty_parent_info(self):
901
935
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
902
936
                                                    len(self._ghosts))
1127
1161
            raise
1128
1162
        return result
1129
1163
 
 
1164
    def update_basis_by_delta(self, delta, new_revid):
 
1165
        """Update the parents of this tree after a commit.
 
1166
 
 
1167
        This gives the tree one parent, with revision id new_revid. The
 
1168
        inventory delta is applied to the current basis tree to generate the
 
1169
        inventory for the parent new_revid, and all other parent trees are
 
1170
        discarded.
 
1171
 
 
1172
        Note that an exception during the operation of this method will leave
 
1173
        the dirstate in a corrupt state where it should not be saved.
 
1174
 
 
1175
        Finally, we expect all changes to be synchronising the basis tree with
 
1176
        the working tree.
 
1177
 
 
1178
        :param new_revid: The new revision id for the trees parent.
 
1179
        :param delta: An inventory delta (see apply_inventory_delta) describing
 
1180
            the changes from the current left most parent revision to new_revid.
 
1181
        """
 
1182
        self._read_dirblocks_if_needed()
 
1183
        self._discard_merge_parents()
 
1184
        if self._ghosts != []:
 
1185
            raise NotImplementedError(self.update_basis_by_delta)
 
1186
        if len(self._parents) == 0:
 
1187
            # setup a blank tree, the most simple way.
 
1188
            empty_parent = DirState.NULL_PARENT_DETAILS
 
1189
            for entry in self._iter_entries():
 
1190
                entry[1].append(empty_parent)
 
1191
            self._parents.append(new_revid)
 
1192
 
 
1193
        self._parents[0] = new_revid
 
1194
 
 
1195
        delta = sorted(delta, reverse=True)
 
1196
        adds = []
 
1197
        changes = []
 
1198
        deletes = []
 
1199
        # The paths this function accepts are unicode and must be encoded as we
 
1200
        # go.
 
1201
        encode = cache_utf8.encode
 
1202
        inv_to_entry = self._inv_entry_to_details
 
1203
        # delta is now (deletes, changes), (adds) in reverse lexographical
 
1204
        # order.
 
1205
        # deletes in reverse lexographic order are safe to process in situ.
 
1206
        # renames are not, as a rename from any path could go to a path
 
1207
        # lexographically lower, so we transform renames into delete, add pairs,
 
1208
        # expanding them recursively as needed.
 
1209
        # At the same time, to reduce interface friction we convert the input
 
1210
        # inventory entries to dirstate.
 
1211
        
 
1212
        for old_path, new_path, file_id, inv_entry in delta:
 
1213
            if old_path is None:
 
1214
                adds.append((None, encode(new_path), file_id,
 
1215
                    inv_to_entry(inv_entry)))
 
1216
            elif new_path is None:
 
1217
                deletes.append((encode(old_path), None, file_id, None))
 
1218
            elif old_path != new_path:
 
1219
                # Renames:
 
1220
                # Because renames must preserve their children we must have
 
1221
                # processed all reloations and removes before hand. The sort
 
1222
                # order ensures we've examined the child paths, but we also
 
1223
                # have to execute the removals, or the split to an add/delete
 
1224
                # pair will result in the deleted item being reinserted, or
 
1225
                # renamed items being reinserted twice - and possibly at the
 
1226
                # wrong place. Splitting into a delete/add pair also simplifies
 
1227
                # the handling of entries with ('f', ...), ('r' ...) because
 
1228
                # the target of the 'r' is old_path here, and we add that to
 
1229
                # deletes, meaning that the add handler does not need to check
 
1230
                # for 'r' items on every pass.
 
1231
                self._update_basis_apply_deletes(deletes)
 
1232
                deletes = []
 
1233
                new_path_utf8 = encode(new_path)
 
1234
                # Split into an add/delete pair recursively.
 
1235
                adds.append((None, new_path_utf8, file_id,
 
1236
                    inv_to_entry(inv_entry)))
 
1237
                # Remove the current contents of the tree at orig_path, and
 
1238
                # reinsert at the correct new path.
 
1239
                new_deletes = list(reversed(list(self._iter_child_entries(1,
 
1240
                    encode(old_path)))))
 
1241
                for entry in new_deletes:
 
1242
                    source_path = '/'.join(entry[0][0:2])
 
1243
                    target_path = new_path_utf8 + source_path[len(old_path):]
 
1244
                    adds.append((None, target_path, entry[0][2], entry[1][1]))
 
1245
                    deletes.append((source_path,  None, entry[0][2], None))
 
1246
                deletes.append((encode(old_path), None, file_id, None))
 
1247
            else:
 
1248
                changes.append((encode(old_path), encode(new_path), file_id,
 
1249
                    inv_to_entry(inv_entry)))
 
1250
 
 
1251
        self._update_basis_apply_deletes(deletes)
 
1252
        self._update_basis_apply_changes(changes)
 
1253
        self._update_basis_apply_adds(adds)
 
1254
 
 
1255
        # remove all deletes
 
1256
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1257
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1258
        return
 
1259
 
 
1260
    def _update_basis_apply_adds(self, adds):
 
1261
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
 
1262
 
 
1263
        They may be adds, or renames that have been split into add/delete
 
1264
        pairs.
 
1265
 
 
1266
        :param adds: A sequence of adds. Each add is a tuple:
 
1267
            (None, new_path_utf8, file_id, (entry_details))
 
1268
        """
 
1269
        # Adds are accumulated partly from renames, so can be in any input
 
1270
        # order - sort it.
 
1271
        adds.sort()
 
1272
        # adds is now in lexographic order, which places all parents before
 
1273
        # their children, so we can process it linearly.
 
1274
        absent = ('r', 'a')
 
1275
        for old_path, new_path, file_id, new_details in adds:
 
1276
            assert old_path is None
 
1277
            # the entry for this file_id must be in tree 0.
 
1278
            entry = self._get_entry(0, file_id, new_path)
 
1279
            if entry[0][2] != file_id:
 
1280
                raise errors.BzrError('dirstate: cannot apply delta, working'
 
1281
                    ' tree does not contain new entry %r %r' %
 
1282
                    (new_path, file_id))
 
1283
            if entry[1][1][0] not in absent:
 
1284
                raise errors.BzrError('dirstate: inconsistent delta, with '
 
1285
                    'tree 0. %r %r' % (new_path, file_id))
 
1286
            # We don't need to update the target of an 'r' because the handling
 
1287
            # of renames turns all 'r' situations into a delete at the original
 
1288
            # location.
 
1289
            entry[1][1] = new_details
 
1290
 
 
1291
    def _update_basis_apply_changes(self, changes):
 
1292
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
 
1293
 
 
1294
        :param adds: A sequence of changes. Each change is a tuple:
 
1295
            (path_utf8, path_utf8, file_id, (entry_details))
 
1296
        """
 
1297
        absent = ('a', 'r')
 
1298
        for old_path, new_path, file_id, new_details in changes:
 
1299
            assert old_path == new_path
 
1300
            # the entry for this file_id must be in tree 0.
 
1301
            entry = self._get_entry(0, file_id, new_path)
 
1302
            if entry[0][2] != file_id:
 
1303
                raise errors.BzrError('dirstate: cannot apply delta, working'
 
1304
                    ' tree does not contain new entry %r %r' %
 
1305
                    (new_path, file_id))
 
1306
            if (entry[1][0][0] in absent or
 
1307
                entry[1][1][0] in absent):
 
1308
                raise errors.BzrError('dirstate: inconsistent delta, with '
 
1309
                    'tree 0. %r %r' % (new_path, file_id))
 
1310
            entry[1][1] = new_details
 
1311
 
 
1312
    def _update_basis_apply_deletes(self, deletes):
 
1313
        """Apply a sequence of deletes to tree 1 during update_basis_by_delta.
 
1314
 
 
1315
        They may be deletes, or renames that have been split into add/delete
 
1316
        pairs.
 
1317
 
 
1318
        :param adds: A sequence of deletes. Each delete is a tuple:
 
1319
            (old_path_utf8, None, file_id, None)
 
1320
        """
 
1321
        absent = ('r', 'a')
 
1322
        # Deletes are accumulated in lexographical order.
 
1323
        for old_path, new_path, file_id, _ in deletes:
 
1324
            assert new_path is None
 
1325
            # the entry for this file_id must be in tree 1.
 
1326
            dirname, basename = osutils.split(old_path)
 
1327
            block_index, entry_index, dir_present, file_present = \
 
1328
                self._get_block_entry_index(dirname, basename, 1)
 
1329
            if not file_present:
 
1330
                raise errors.BzrError('dirstate: cannot apply delta, basis'
 
1331
                    ' tree does not contain new entry %r %r' %
 
1332
                    (old_path, file_id))
 
1333
            entry = self._dirblocks[block_index][1][entry_index]
 
1334
            if entry[0][2] != file_id:
 
1335
                raise errors.BzrError('mismatched file_id in tree 1 %r %r' %
 
1336
                    (old_path, file_id))
 
1337
            if entry[1][0][0] not in absent:
 
1338
                raise errors.BzrError('dirstate: inconsistent delta, with '
 
1339
                    'tree 0. %r %r' % (old_path, file_id))
 
1340
            del self._dirblocks[block_index][1][entry_index]
 
1341
 
1130
1342
    def update_entry(self, entry, abspath, stat_value,
1131
1343
                     _stat_to_minikind=_stat_to_minikind,
1132
1344
                     _pack_stat=pack_stat):
1526
1738
            raise Exception("can't pack %s" % inv_entry)
1527
1739
        return (minikind, fingerprint, size, executable, tree_data)
1528
1740
 
 
1741
    def _iter_child_entries(self, tree_index, path_utf8):
 
1742
        """Iterate over all the entries that are children of path_utf.
 
1743
 
 
1744
        This only returns entries that are present (not in 'a', 'r') in 
 
1745
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
 
1746
        results may differ from that obtained if paths were statted to
 
1747
        determine what ones were directories.
 
1748
 
 
1749
        Asking for the children of a non-directory will return an empty
 
1750
        iterator.
 
1751
        """
 
1752
        pending_dirs = []
 
1753
        next_pending_dirs = [path_utf8]
 
1754
        absent = ('r', 'a')
 
1755
        while next_pending_dirs:
 
1756
            pending_dirs = next_pending_dirs
 
1757
            next_pending_dirs = []
 
1758
            for path in pending_dirs:
 
1759
                block_index, present = self._find_block_index_from_key(
 
1760
                    (path, '', ''))
 
1761
                if not present:
 
1762
                    # children of a non-directory asked for.
 
1763
                    continue
 
1764
                block = self._dirblocks[block_index]
 
1765
                for entry in block[1]:
 
1766
                    kind = entry[1][tree_index][0]
 
1767
                    if kind not in absent:
 
1768
                        yield entry
 
1769
                    if kind == 'd':
 
1770
                        next_pending_dirs.append('/'.join(entry[0][0:2]))
 
1771
    
1529
1772
    def _iter_entries(self):
1530
1773
        """Iterate over all the entries in the dirstate.
1531
1774