← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-07-20 08:56:45 UTC
  • mfrom: (4526.9.23 apply-inventory-delta)
  • Revision ID: pqm@pqm.ubuntu.com-20090720085645-54mtgybxua0yx6hw
(robertc) Add checks for inventory deltas which try to ensure that
        deltas that are not an exact fit are not applied. (Robert
        Collins, bug 397705, bug 367633)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/dirstate.py
204
204
import bisect
205
205
import binascii
206
206
import errno
 
207
import operator
207
208
import os
208
209
from stat import S_IEXEC
209
210
import stat
1277
1278
    def update_by_delta(self, delta):
1278
1279
        """Apply an inventory delta to the dirstate for tree 0
1279
1280
 
 
1281
        This is the workhorse for apply_inventory_delta in dirstate based
 
1282
        trees.
 
1283
 
1280
1284
        :param delta: An inventory delta.  See Inventory.apply_delta for
1281
1285
            details.
1282
1286
        """
1283
1287
        self._read_dirblocks_if_needed()
 
1288
        encode = cache_utf8.encode
1284
1289
        insertions = {}
1285
1290
        removals = {}
1286
 
        for old_path, new_path, file_id, inv_entry in sorted(delta, reverse=True):
 
1291
        # Accumulate parent references (path_utf8, id), to check for parentless
 
1292
        # items or items placed under files/links/tree-references. We get
 
1293
        # references from every item in the delta that is not a deletion and
 
1294
        # is not itself the root.
 
1295
        parents = set()
 
1296
        # Added ids must not be in the dirstate already. This set holds those
 
1297
        # ids.
 
1298
        new_ids = set()
 
1299
        # This loop transforms the delta to single atomic operations that can
 
1300
        # 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):
1287
1308
            if (file_id in insertions) or (file_id in removals):
1288
1309
                raise errors.InconsistentDelta(old_path or new_path, file_id,
1289
1310
                    "repeated file_id")
1290
1311
            if old_path is not None:
1291
1312
                old_path = old_path.encode('utf-8')
1292
1313
                removals[file_id] = old_path
 
1314
            else:
 
1315
                new_ids.add(file_id)
1293
1316
            if new_path is not None:
 
1317
                if inv_entry is None:
 
1318
                    raise errors.InconsistentDelta(new_path, file_id,
 
1319
                        "new_path with no entry")
1294
1320
                new_path = new_path.encode('utf-8')
1295
 
                dirname, basename = osutils.split(new_path)
1296
 
                key = (dirname, basename, file_id)
 
1321
                dirname_utf8, basename = osutils.split(new_path)
 
1322
                if basename:
 
1323
                    parents.add((dirname_utf8, inv_entry.parent_id))
 
1324
                key = (dirname_utf8, basename, file_id)
1297
1325
                minikind = DirState._kind_to_minikind[inv_entry.kind]
1298
1326
                if minikind == 't':
1299
1327
                    fingerprint = inv_entry.reference_revision
1321
1349
                                                  child_basename)
1322
1350
                    insertions[child[0][2]] = (key, minikind, executable,
1323
1351
                                               fingerprint, new_child_path)
1324
 
        self._apply_removals(removals.values())
1325
 
        self._apply_insertions(insertions.values())
 
1352
        self._check_delta_ids_absent(new_ids, delta, 0)
 
1353
        try:
 
1354
            self._apply_removals(removals.iteritems())
 
1355
            self._apply_insertions(insertions.values())
 
1356
            # Validate parents
 
1357
            self._after_delta_check_parents(parents, 0)
 
1358
        except errors.BzrError, e:
 
1359
            self._changes_aborted = True
 
1360
            if 'integrity error' not in str(e):
 
1361
                raise
 
1362
            # _get_entry raises BzrError when a request is inconsistent; we
 
1363
            # want such errors to be shown as InconsistentDelta - and that 
 
1364
            # fits the behaviour we trigger.
 
1365
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1326
1366
 
1327
1367
    def _apply_removals(self, removals):
1328
 
        for path in sorted(removals, reverse=True):
 
1368
        for file_id, path in sorted(removals, reverse=True,
 
1369
            key=operator.itemgetter(1)):
1329
1370
            dirname, basename = osutils.split(path)
1330
1371
            block_i, entry_i, d_present, f_present = \
1331
1372
                self._get_block_entry_index(dirname, basename, 0)
1332
 
            entry = self._dirblocks[block_i][1][entry_i]
 
1373
            try:
 
1374
                entry = self._dirblocks[block_i][1][entry_i]
 
1375
            except IndexError:
 
1376
                self._changes_aborted = True
 
1377
                raise errors.InconsistentDelta(path, file_id,
 
1378
                    "Wrong path for old path.")
 
1379
            if not f_present or entry[1][0][0] in 'ar':
 
1380
                self._changes_aborted = True
 
1381
                raise errors.InconsistentDelta(path, file_id,
 
1382
                    "Wrong path for old path.")
 
1383
            if file_id != entry[0][2]:
 
1384
                self._changes_aborted = True
 
1385
                raise errors.InconsistentDelta(path, file_id,
 
1386
                    "Attempt to remove path has wrong id - found %r."
 
1387
                    % entry[0][2])
1333
1388
            self._make_absent(entry)
1334
1389
            # See if we have a malformed delta: deleting a directory must not
1335
1390
            # leave crud behind. This increases the number of bisects needed
1343
1398
                # be due to it being in a parent tree, or a corrupt delta.
1344
1399
                for child_entry in self._dirblocks[block_i][1]:
1345
1400
                    if child_entry[1][0][0] not in ('r', 'a'):
 
1401
                        self._changes_aborted = True
1346
1402
                        raise errors.InconsistentDelta(path, entry[0][2],
1347
1403
                            "The file id was deleted but its children were "
1348
1404
                            "not deleted.")
1349
1405
 
1350
1406
    def _apply_insertions(self, adds):
1351
 
        for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
1352
 
            self.update_minimal(key, minikind, executable, fingerprint,
1353
 
                                path_utf8=path_utf8)
 
1407
        try:
 
1408
            for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
 
1409
                self.update_minimal(key, minikind, executable, fingerprint,
 
1410
                                    path_utf8=path_utf8)
 
1411
        except errors.NotVersionedError:
 
1412
            self._changes_aborted = True
 
1413
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
 
1414
                "Missing parent")
1354
1415
 
1355
1416
    def update_basis_by_delta(self, delta, new_revid):
1356
1417
        """Update the parents of this tree after a commit.
1400
1461
        # At the same time, to reduce interface friction we convert the input
1401
1462
        # inventory entries to dirstate.
1402
1463
        root_only = ('', '')
1403
 
        # Accumulate parent references (path and id), to check for parentless
 
1464
        # Accumulate parent references (path_utf8, id), to check for parentless
1404
1465
        # items or items placed under files/links/tree-references. We get
1405
1466
        # references from every item in the delta that is not a deletion and
1406
1467
        # is not itself the root.
1407
1468
        parents = set()
 
1469
        # Added ids must not be in the dirstate already. This set holds those
 
1470
        # ids.
 
1471
        new_ids = set()
1408
1472
        for old_path, new_path, file_id, inv_entry in delta:
1409
1473
            if inv_entry is not None and file_id != inv_entry.file_id:
1410
1474
                raise errors.InconsistentDelta(new_path, file_id,
1411
1475
                    "mismatched entry file_id %r" % inv_entry)
1412
1476
            if new_path is not None:
 
1477
                if inv_entry is None:
 
1478
                    raise errors.InconsistentDelta(new_path, file_id,
 
1479
                        "new_path with no entry")
1413
1480
                new_path_utf8 = encode(new_path)
1414
1481
                # note the parent for validation
1415
1482
                dirname_utf8, basename_utf8 = osutils.split(new_path_utf8)
1418
1485
            if old_path is None:
1419
1486
                adds.append((None, encode(new_path), file_id,
1420
1487
                    inv_to_entry(inv_entry), True))
 
1488
                new_ids.add(file_id)
1421
1489
            elif new_path is None:
1422
1490
                deletes.append((encode(old_path), None, file_id, None, True))
1423
1491
            elif (old_path, new_path) != root_only:
1466
1534
                # of everything.
1467
1535
                changes.append((encode(old_path), encode(new_path), file_id,
1468
1536
                    inv_to_entry(inv_entry)))
1469
 
 
 
1537
        self._check_delta_ids_absent(new_ids, delta, 1)
1470
1538
        try:
1471
1539
            # Finish expunging deletes/first half of renames.
1472
1540
            self._update_basis_apply_deletes(deletes)
1475
1543
            # Apply in-situ changes.
1476
1544
            self._update_basis_apply_changes(changes)
1477
1545
            # Validate parents
1478
 
            self._update_basis_check_parents(parents)
 
1546
            self._after_delta_check_parents(parents, 1)
1479
1547
        except errors.BzrError, e:
 
1548
            self._changes_aborted = True
1480
1549
            if 'integrity error' not in str(e):
1481
1550
                raise
1482
1551
            # _get_entry raises BzrError when a request is inconsistent; we
1484
1553
            # fits the behaviour we trigger. Partof this is driven by dirstate
1485
1554
            # only supporting deltas that turn the basis into a closer fit to
1486
1555
            # the active tree.
1487
 
            self._changes_aborted = True
1488
1556
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
1489
1557
 
1490
1558
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1492
1560
        self._id_index = None
1493
1561
        return
1494
1562
 
 
1563
    def _check_delta_ids_absent(self, new_ids, delta, tree_index):
 
1564
        """Check that none of the file_ids in new_ids are present in a tree."""
 
1565
        if not new_ids:
 
1566
            return
 
1567
        id_index = self._get_id_index()
 
1568
        for file_id in new_ids:
 
1569
            for key in id_index.get(file_id, []):
 
1570
                block_i, entry_i, d_present, f_present = \
 
1571
                    self._get_block_entry_index(key[0], key[1], tree_index)
 
1572
                if not f_present:
 
1573
                    # In a different tree
 
1574
                    continue
 
1575
                entry = self._dirblocks[block_i][1][entry_i]
 
1576
                if entry[0][2] != file_id:
 
1577
                    # Different file_id, so not what we want.
 
1578
                    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,
 
1583
                    "This file_id is new in the delta but already present in "
 
1584
                    "the target")
 
1585
 
1495
1586
    def _update_basis_apply_adds(self, adds):
1496
1587
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
1497
1588
 
1562
1653
        null = DirState.NULL_PARENT_DETAILS
1563
1654
        for old_path, new_path, file_id, _, real_delete in deletes:
1564
1655
            if real_delete != (new_path is None):
 
1656
                self._changes_aborted = True
1565
1657
                raise AssertionError("bad delete delta")
1566
1658
            # the entry for this file_id must be in tree 1.
1567
1659
            dirname, basename = osutils.split(old_path)
1600
1692
                    # it is being resurrected here, so blank it out temporarily.
1601
1693
                    self._dirblocks[block_index][1][entry_index][1][1] = null
1602
1694
 
1603
 
    def _update_basis_check_parents(self, parents):
1604
 
        """Check that parents required by the delta are all intact."""
 
1695
    def _after_delta_check_parents(self, parents, index):
 
1696
        """Check that parents required by the delta are all intact.
 
1697
        
 
1698
        :param parents: An iterable of (path_utf8, file_id) tuples which are
 
1699
            required to be present in tree 'index' at path_utf8 with id file_id
 
1700
            and be a directory.
 
1701
        :param index: The column in the dirstate to check for parents in.
 
1702
        """
1605
1703
        for dirname_utf8, file_id in parents:
1606
1704
            # Get the entry - the ensures that file_id, dirname_utf8 exists and
1607
1705
            # has the right file id.
1608
 
            entry = self._get_entry(1, file_id, dirname_utf8)
 
1706
            entry = self._get_entry(index, file_id, dirname_utf8)
1609
1707
            if entry[1] is None:
1610
1708
                self._changes_aborted = True
1611
1709
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1612
1710
                    file_id, "This parent is not present.")
1613
1711
            # Parents of things must be directories
1614
 
            if entry[1][1][0] != 'd':
 
1712
            if entry[1][index][0] != 'd':
1615
1713
                self._changes_aborted = True
1616
1714
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
1617
1715
                    file_id, "This parent is not a directory.")
2486
2584
                        new_path_utf8.decode('utf8'))
2487
2585
                self.update_minimal(new_entry_key, current_new_minikind,
2488
2586
                    executable=current_new[1].executable,
2489
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2587
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2588
                    fullscan=True)
2490
2589
                current_new = advance(new_iterator)
2491
2590
            elif not current_new:
2492
2591
                # new is finished
2511
2610
                            new_path_utf8.decode('utf8'))
2512
2611
                    self.update_minimal(current_old[0], current_new_minikind,
2513
2612
                        executable=current_new[1].executable,
2514
 
                        path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2613
                        path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2614
                        fullscan=True)
2515
2615
                # both sides are dealt with, move on
2516
2616
                current_old = advance(old_iterator)
2517
2617
                current_new = advance(new_iterator)
2525
2625
                        new_path_utf8.decode('utf8'))
2526
2626
                self.update_minimal(new_entry_key, current_new_minikind,
2527
2627
                    executable=current_new[1].executable,
2528
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2628
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2629
                    fullscan=True)
2529
2630
                current_new = advance(new_iterator)
2530
2631
            else:
2531
2632
                # we've advanced past the place where the old key would be,
2595
2696
        return last_reference
2596
2697
 
2597
2698
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2598
 
                       packed_stat=None, size=0, path_utf8=None):
 
2699
        packed_stat=None, size=0, path_utf8=None, fullscan=False):
2599
2700
        """Update an entry to the state in tree 0.
2600
2701
 
2601
2702
        This will either create a new entry at 'key' or update an existing one.
2612
2713
        :param size: Size information for new entry
2613
2714
        :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
2614
2715
                extra computation.
 
2716
        :param fullscan: If True then a complete scan of the dirstate is being
 
2717
            done and checking for duplicate rows should not be done. This
 
2718
            should only be set by set_state_from_inventory and similar methods.
2615
2719
 
2616
2720
        If packed_stat and fingerprint are not given, they're invalidated in
2617
2721
        the entry.
2626
2730
        new_details = (minikind, fingerprint, size, executable, packed_stat)
2627
2731
        id_index = self._get_id_index()
2628
2732
        if not present:
 
2733
            # New record. Check there isn't a entry at this path already.
 
2734
            if not fullscan:
 
2735
                low_index, _ = self._find_entry_index(key[0:2] + ('',), block)
 
2736
                while low_index < len(block):
 
2737
                    entry = block[low_index]
 
2738
                    if entry[0][0:2] == key[0:2]:
 
2739
                        if entry[1][0][0] not in 'ar':
 
2740
                            # This entry has the same path (but a different id) as
 
2741
                            # the new entry we're adding, and is present in ths
 
2742
                            # tree.
 
2743
                            raise errors.InconsistentDelta(
 
2744
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
 
2745
                                "Attempt to add item at path already occupied by "
 
2746
                                "id %r" % entry[0][2])
 
2747
                        low_index += 1
 
2748
                    else:
 
2749
                        break
2629
2750
            # new entry, synthesis cross reference here,
2630
2751
            existing_keys = id_index.setdefault(key[2], set())
2631
2752
            if not existing_keys: