← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

Significant steps back to operation.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/dirstate.py
459
459
 
460
460
        :return: The block index, True if the block for the key is present.
461
461
        """
462
 
        block_index = bisect.bisect_left(self._dirblocks, (dirname, []))
 
462
        block_index = bisect.bisect_left(self._dirblocks, (key[0], []))
463
463
        present = (block_index < len(self._dirblocks) and
464
 
            self._dirblocks[block_index][0] == dirname)
 
464
            self._dirblocks[block_index][0] == key[0])
465
465
        return block_index, present
466
466
 
467
467
    def _find_dirblock_index(self, dirname):
1183
1183
        # incremental algorithm:
1184
1184
        # two iterators: current data and new data, both in dirblock order. 
1185
1185
        new_iterator = new_inv.iter_entries_by_dir()
1186
 
        # we will be modifying the dirstate, so we need a stable iterator. In future we might write one, for now we just clone the state into a list
 
1186
        # we will be modifying the dirstate, so we need a stable iterator. In
 
1187
        # future we might write one, for now we just clone the state into a
 
1188
        # list - which is a shallow copy, so each 
1187
1189
        old_iterator = iter(list(self._iter_entries()))
1188
1190
        # both must have roots so this is safe:
1189
1191
        current_new = new_iterator.next()
1190
1192
        current_old = old_iterator.next()
1191
1193
        def advance(iterator):
1192
1194
            try:
1193
 
                return old_iterator.next()
 
1195
                return iterator.next()
1194
1196
            except StopIteration:
1195
1197
                return None
1196
1198
        while current_new or current_old:
1197
1199
            # skip entries in old that are not really there
1198
 
            if current_old and current_old[1][0] in ('relocated', 'absent'):
 
1200
            if current_old and current_old[1][0][0] in ('relocated', 'absent'):
1199
1201
                current_old = advance(old_iterator)
1200
1202
                continue
1201
1203
            if current_new:
1202
1204
                # convert new into dirblock style
1203
 
                new_dirname, new_basename = os.path.split(current_new[0].encode('utf8'))
 
1205
                new_path_utf8 = current_new[0].encode('utf8')
 
1206
                new_dirname, new_basename = os.path.split(new_path_utf8)
1204
1207
                new_id = current_new[1].file_id.encode('utf8')
1205
1208
                new_entry_key = (new_dirname, new_basename, new_id)
 
1209
            else:
 
1210
                # for safety disable variables
 
1211
                new_path_utf8 = new_dirname = new_basename = new_id = new_entry_key = None
1206
1212
            # 5 cases, we dont have a value that is strictly greater than everything, so
1207
1213
            # we make both end conditions explicit
1208
1214
            if not current_old:
1209
1215
                # old is finished: insert current_new into the state.
1210
1216
                self.update_minimal(new_entry_key, current_new[1].kind,
1211
 
                    executable=current_new[1].executable, id_index=id_index)
 
1217
                    num_present_parents, executable=current_new[1].executable,
 
1218
                    id_index=id_index, path_utf8=new_path_utf8)
1212
1219
                current_new = advance(new_iterator)
1213
1220
            elif not current_new:
1214
1221
                # new is finished
1215
 
                import pdb;pdb.set_trace()
 
1222
                self._make_absent(num_present_parents, current_old, id_index)
 
1223
                current_old = advance(old_iterator)
1216
1224
            elif new_entry_key == current_old[0]:
1217
1225
                # same -  common case
1218
1226
                # TODO: update the record if anything significant has changed.
1219
 
                # the minimal required trigger is if the execute bit has
1220
 
                # changed.
1221
 
                if current_old[1][0][3] != current_new[1].executable:
1222
 
                    import pdb;pdb.set_trace()
 
1227
                # the minimal required trigger is if the execute bit or cached
 
1228
                # kind has changed.
 
1229
                if (current_old[1][0][3] != current_new[1].executable or
 
1230
                    current_old[1][0][0] != current_new[1].kind):
 
1231
                    self.update_minimal(current_old[0], current_new[1].kind,
 
1232
                        num_present_parents,
 
1233
                        executable=current_new[1].executable,
 
1234
                        id_index=id_index, path_utf8=new_path_utf8)
1223
1235
                # both sides are dealt with, move on
1224
1236
                current_old = advance(old_iterator)
1225
1237
                current_new = advance(new_iterator)
1226
1238
            elif new_entry_key < current_old[0]:
1227
 
                # new comes before 
1228
 
                import pdb;pdb.set_trace()
 
1239
                # new comes before:
 
1240
                # add a entry for this and advance new
 
1241
                self.update_minimal(new_entry_key, current_new[1].kind,
 
1242
                    num_present_parents, executable=current_new[1].executable,
 
1243
                    id_index=id_index, path_utf8=new_path_utf8)
 
1244
                current_new = advance(new_iterator)
1229
1245
            else:
1230
1246
                # old comes before:
1231
 
                # remove old from the state, advance old
1232
 
                # to remove old, we have two conditions.
1233
 
                # either its the last reference to this path that we are
1234
 
                # removing, or its not. If its the last reference, we remove
1235
 
                # the entire row and remove the path from the id mapping. If
1236
 
                # its not the last reference, we just set it to absent.
1237
 
                last_reference = True
1238
 
                for lookup_index in xrange(1, num_present_parents + 1):
1239
 
                    if current_old[1][lookup_index] not in ('absent', 'relocated'):
1240
 
                        last_reference = False
1241
 
                        break
1242
 
                if not last_reference:
1243
 
                    import pdb;pdb.set_trace()
1244
 
                    # common case, theres a parent at this path
1245
 
                    current_old[1][0] = DirState.NULL_PARENT_DETAILS
1246
 
                else:
1247
 
                    # there are no more references at this path
1248
 
                    id_index[current_old[0][2]].remove(current_old[0])
1249
 
                    # are there others (which will need to be changed
1250
 
                    # from relocated to absent for index 0)?
1251
 
                    if len(id_index[current_old[0][2]]):
1252
 
                        import pdb;pdb.set_trace()
1253
 
                    block = self._find_block(current_old[0])
1254
 
                    entry_index, present = self._find_entry_index(key, block)
1255
 
                    assert present
1256
 
                    block.pop(entry_index)
 
1247
                self._make_absent(num_present_parents, current_old, id_index)
1257
1248
                current_old = advance(old_iterator)
1258
1249
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1259
1250
 
1260
 
    def update_minimal(self, key, kind, executable=False, fingerprint='',
1261
 
        packed_stat=None, size=0, id_index=None):
 
1251
    def _make_absent(self, num_present_parents, current_old, id_index):
 
1252
        # remove old from the state, advance old
 
1253
        # to remove old, we have two conditions:
 
1254
        # either its the last reference to this path that we are
 
1255
        # removing, or its not. If its the last reference, we remove
 
1256
        # the entire row and remove the path from the id mapping. If
 
1257
        # its not the last reference, we just set it to absent.
 
1258
        last_reference = True
 
1259
        for lookup_index in xrange(1, num_present_parents + 1):
 
1260
            if current_old[1][lookup_index] not in ('absent', 'relocated'):
 
1261
                last_reference = False
 
1262
                break
 
1263
        if not last_reference:
 
1264
            # common case, theres a parent at this path
 
1265
            current_old[1][0] = DirState.NULL_PARENT_DETAILS
 
1266
        else:
 
1267
            # there are no more references at this path
 
1268
            id_index[current_old[0][2]].remove(current_old[0])
 
1269
            # are there others (which will need to be changed
 
1270
            # from relocated to absent for index 0)?
 
1271
            for update_key in id_index[current_old[0][2]]:
 
1272
                # update the entry for 0 to say absent: there is a parent at
 
1273
                # that path, but nothing in this tree for that file id anymore.
 
1274
                update_block_index, present = \
 
1275
                    self._find_block_index_from_key(update_key)
 
1276
                assert present
 
1277
                update_entry_index, present = \
 
1278
                    self._find_entry_index(update_key, self._dirblocks[update_block_index][1])
 
1279
                assert present
 
1280
                update_tree_details = self._dirblocks[update_block_index][1][update_entry_index][1]
 
1281
                # it must currently be relocated
 
1282
                assert update_tree_details[0][0] == 'relocated'
 
1283
                update_tree_details[0] = DirState.NULL_PARENT_DETAILS
 
1284
            block = self._find_block(current_old[0])
 
1285
            entry_index, present = self._find_entry_index(current_old[0], block[1])
 
1286
            assert present
 
1287
            block[1].pop(entry_index)
 
1288
 
 
1289
    def update_minimal(self, key, kind, num_present_parents, executable=False,
 
1290
        fingerprint='', packed_stat=None, size=0, id_index=None,
 
1291
        path_utf8=None):
1262
1292
        """Update an entry to the state in tree 0."""
1263
 
        self._read_dirblocks_if_needed()
1264
1293
        if key[0:2] == ('', ''):
1265
1294
            block = self._root_entries
1266
1295
        else:
1269
1298
            packed_stat = DirState.NULLSTAT
1270
1299
        entry_index, present = self._find_entry_index(key, block)
1271
1300
        new_details = (kind, fingerprint, size, executable, packed_stat)
 
1301
        assert id_index, 'need an id index to do updates for now !'
1272
1302
        if not present:
1273
1303
            # new entry, synthesis cross reference here,
1274
 
            assert id_index, 'need an id index to generate a new entry'
1275
 
            existing_keys = id_index.setdefault(key, set())
 
1304
            existing_keys = id_index.setdefault(key[2], set())
1276
1305
            if not existing_keys:
1277
1306
                # not currently in the state, simplest case
1278
1307
                new_entry = key, [new_details] + self._empty_parent_info()
1279
1308
            else:
1280
 
                import pdb;pdb.set_trace()
 
1309
                # present at one or more existing other paths.
 
1310
                # grab one of them and use it to generate parent
 
1311
                # relocation/absent entries.
 
1312
                new_entry = key, [new_details]
 
1313
                for other_key in existing_keys:
 
1314
                    # change the record at other to be a pointer to this new
 
1315
                    # record. The loop looks similar to the change to
 
1316
                    # relocations when updating an existing record but its not:
 
1317
                    # the test for existing kinds is different: this can be
 
1318
                    # factored out to a helper though.
 
1319
                    other_block_index, present = self._find_block_index_from_key(other_key)
 
1320
                    assert present
 
1321
                    other_entry_index, present = self._find_entry_index(other_key, self._dirblocks[other_block_index][1])
 
1322
                    assert present
 
1323
                    self._dirblocks[other_block_index][1][other_entry_index][1][0] = \
 
1324
                        ('relocated', path_utf8, 0, False, '')
1281
1325
 
 
1326
                for lookup_index in xrange(1, num_present_parents + 1):
 
1327
                    # grab any one entry, use it to find the right path.
 
1328
                    # TODO: optimise this to reduce memory use in highly 
 
1329
                    # fragmented situations by reusing the relocation
 
1330
                    # records.
 
1331
                    update_block_index, present = \
 
1332
                        self._find_block_index_from_key(other_key)
 
1333
                    assert present
 
1334
                    update_entry_index, present = \
 
1335
                        self._find_entry_index(other_key, self._dirblocks[update_block_index][1])
 
1336
                    assert present
 
1337
                    update_details = self._dirblocks[update_block_index][1][update_entry_index][1][lookup_index]
 
1338
                    if update_details[0] in ('relocated', 'absent'):
 
1339
                        # its a pointer or absent in lookup_index's tree, use
 
1340
                        # it as is.
 
1341
                        new_entry[1].append(update_details)
 
1342
                    else:
 
1343
                        # we have the right key, make a pointer to it.
 
1344
                        pointer_path = os.path.join(other_key[0:2])
 
1345
                        new_details.append(('relocated', pointer_path, 0, False, ''))
1282
1346
            block.insert(entry_index, new_entry)
1283
1347
            existing_keys.add(key)
1284
1348
        else:
1285
1349
            # Does the new state matter? 
1286
 
            import pdb;pdb.set_trace()
1287
1350
            block[entry_index][1][0] = new_details
 
1351
            # parents cannot be affected by what we do.
 
1352
            # other occurences of this id can be found 
 
1353
            # from the id index.
 
1354
            # ---
 
1355
            # tree index consistency: All other paths for this id in this tree
 
1356
            # index must point to the correct path. We have to loop here because
 
1357
            # we may have passed entries in the state with this file id already
 
1358
            # that were absent - where parent entries are - and they need to be
 
1359
            # converted to relocated.
 
1360
            assert path_utf8 is not None
 
1361
            for entry_key in id_index.setdefault(key[2], set()):
 
1362
                # TODO:PROFILING: It might be faster to just update
 
1363
                # rather than checking if we need to, and then overwrite
 
1364
                # the one we are located at.
 
1365
                if entry_key != key:
 
1366
                    # this file id is at a different path in one of the
 
1367
                    # other trees, so put absent pointers there
 
1368
                    # This is the vertical axis in the matrix, all pointing
 
1369
                    # to the real path.
 
1370
                    block_index, present = self._find_block_index_from_key(entry_key)
 
1371
                    assert present
 
1372
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
 
1373
                    assert present
 
1374
                    self._dirblocks[block_index][1][entry_index][1][0] = \
 
1375
                        ('relocated', path_utf8, 0, False, '')
 
1376
 
1288
1377
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1289
1378
 
1290
1379