← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

Merge from bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1376
1376
            raise KnitCorrupt(self, "Cannot do delta compression without "
1377
1377
                "parent tracking.")
1378
1378
 
1379
 
    def _get_entries(self, version_ids, check_present=False):
1380
 
        """Get the entries for version_ids."""
1381
 
        version_ids = set(version_ids)
 
1379
    def _get_entries(self, keys, check_present=False):
 
1380
        """Get the entries for keys.
 
1381
        
 
1382
        :param keys: An iterable of index keys, - 1-tuples.
 
1383
        """
 
1384
        keys = set(keys)
1382
1385
        found_keys = set()
1383
1386
        if self._parents:
1384
 
            for node in self._graph_index.iter_entries(version_ids):
 
1387
            for node in self._graph_index.iter_entries(keys):
1385
1388
                yield node
1386
1389
                found_keys.add(node[0])
1387
1390
        else:
1388
1391
            # adapt parentless index to the rest of the code.
1389
 
            for node in self._graph_index.iter_entries(version_ids):
 
1392
            for node in self._graph_index.iter_entries(keys):
1390
1393
                yield node[0], node[1], ()
1391
1394
                found_keys.add(node[0])
1392
1395
        if check_present:
1393
 
            missing_keys = version_ids.difference(found_keys)
 
1396
            missing_keys = keys.difference(found_keys)
1394
1397
            if missing_keys:
1395
1398
                raise RevisionNotPresent(missing_keys.pop(), self)
1396
1399
 
1400
1403
 
1401
1404
    def _parentless_ancestry(self, versions):
1402
1405
        """Honour the get_ancestry API for parentless knit indices."""
1403
 
        present_keys = self._present_keys(versions)
1404
 
        missing = set(versions).difference(present_keys)
 
1406
        wanted_keys = self._version_ids_to_keys(versions)
 
1407
        present_keys = self._present_keys(wanted_keys)
 
1408
        missing = set(wanted_keys).difference(present_keys)
1405
1409
        if missing:
1406
1410
            raise RevisionNotPresent(missing.pop(), self)
1407
 
        return list(present_keys)
 
1411
        return list(self._keys_to_version_ids(present_keys))
1408
1412
 
1409
1413
    def get_ancestry(self, versions, topo_sorted=True):
1410
1414
        """See VersionedFile.get_ancestry."""
1415
1419
        # get a graph of all the mentioned versions:
1416
1420
        graph = {}
1417
1421
        ghosts = set()
1418
 
        versions = set(versions)
 
1422
        versions = self._version_ids_to_keys(versions)
1419
1423
        pending = set(versions)
1420
1424
        while pending:
1421
1425
            # get all pending nodes
1422
1426
            this_iteration = pending
1423
1427
            new_nodes = self._get_entries(this_iteration)
 
1428
            found = set()
1424
1429
            pending = set()
1425
1430
            for (key, value, node_refs) in new_nodes:
1426
1431
                # dont ask for ghosties - otherwise
1428
1433
                # being entirely ghosted.
1429
1434
                graph[key] = [parent for parent in node_refs[0]
1430
1435
                    if parent not in ghosts]
1431
 
                # queue parents 
1432
 
                pending.update(graph[key])
1433
 
            ghosts.difference_update(graph)
1434
 
            # dont examine known nodes
1435
 
            pending.difference_update(graph)
 
1436
                # queue parents
 
1437
                for parent in graph[key]:
 
1438
                    # dont examine known nodes again
 
1439
                    if parent in graph:
 
1440
                        continue
 
1441
                    pending.add(parent)
 
1442
                found.add(key)
 
1443
            ghosts.update(this_iteration.difference(found))
1436
1444
        if versions.difference(graph):
1437
1445
            raise RevisionNotPresent(versions.difference(graph).pop(), self)
1438
 
        if not topo_sorted:
1439
 
            return graph.keys()
1440
 
        return topo_sort(graph.items())
 
1446
        if topo_sorted:
 
1447
            result_keys = topo_sort(graph.items())
 
1448
        else:
 
1449
            result_keys = graph.iterkeys()
 
1450
        return [key[0] for key in result_keys]
1441
1451
 
1442
1452
    def get_ancestry_with_ghosts(self, versions):
1443
1453
        """See VersionedFile.get_ancestry."""
1447
1457
        # it should be altered to be a index core feature?
1448
1458
        # get a graph of all the mentioned versions:
1449
1459
        graph = {}
1450
 
        versions = set(versions)
 
1460
        versions = self._version_ids_to_keys(versions)
1451
1461
        pending = set(versions)
1452
1462
        while pending:
1453
1463
            # get all pending nodes
1457
1467
            for (key, value, node_refs) in new_nodes:
1458
1468
                graph[key] = node_refs[0]
1459
1469
                # queue parents 
1460
 
                pending.update(graph[key])
 
1470
                for parent in graph[key]:
 
1471
                    # dont examine known nodes again
 
1472
                    if parent in graph:
 
1473
                        continue
 
1474
                    pending.add(parent)
1461
1475
            missing_versions = this_iteration.difference(graph)
1462
1476
            missing_needed = versions.intersection(missing_versions)
1463
1477
            if missing_needed:
1465
1479
            for missing_version in missing_versions:
1466
1480
                # add a key, no parents
1467
1481
                graph[missing_version] = []
1468
 
            # dont examine known nodes
1469
 
            pending.difference_update(graph)
1470
 
        return topo_sort(graph.items())
 
1482
                pending.discard(missing_version) # don't look for it
 
1483
        result_keys = topo_sort(graph.items())
 
1484
        return [key[0] for key in result_keys]
1471
1485
 
1472
1486
    def get_graph(self):
1473
1487
        """Return a list of the node:parents lists from this knit index."""
1474
1488
        if not self._parents:
1475
1489
            return [(key, ()) for key in self.get_versions()]
1476
 
        return [(key, refs[0]) for (key, value, refs) in 
1477
 
            self._graph_index.iter_all_entries()]
 
1490
        result = []
 
1491
        for key, value, refs in self._graph_index.iter_all_entries():
 
1492
            result.append((key[0], tuple([ref[0] for ref in refs[0]])))
 
1493
        return result
1478
1494
 
1479
1495
    def iter_parents(self, version_ids):
1480
1496
        """Iterate through the parents for many version ids.
1486
1502
            the underlying implementation.
1487
1503
        """
1488
1504
        if self._parents:
1489
 
            all_nodes = set(self._get_entries(version_ids))
 
1505
            all_nodes = set(self._get_entries(self._version_ids_to_keys(version_ids)))
1490
1506
            all_parents = set()
1491
1507
            present_parents = set()
1492
1508
            for node in all_nodes:
1499
1515
                parents = []
1500
1516
                for parent in node[2][0]:
1501
1517
                    if parent in present_parents:
1502
 
                        parents.append(parent)
1503
 
                yield node[0], tuple(parents)
 
1518
                        parents.append(parent[0])
 
1519
                yield node[0][0], tuple(parents)
1504
1520
        else:
1505
 
            for node in self._get_entries(version_ids):
1506
 
                yield node[0], ()
 
1521
            for node in self._get_entries(self._version_ids_to_keys(version_ids)):
 
1522
                yield node[0][0], ()
1507
1523
 
1508
1524
    def num_versions(self):
1509
1525
        return len(list(self._graph_index.iter_all_entries()))
1512
1528
 
1513
1529
    def get_versions(self):
1514
1530
        """Get all the versions in the file. not topologically sorted."""
1515
 
        return [node[0] for node in self._graph_index.iter_all_entries()]
 
1531
        return [node[0][0] for node in self._graph_index.iter_all_entries()]
1516
1532
    
1517
1533
    def has_version(self, version_id):
1518
1534
        """True if the version is in the index."""
1519
 
        return len(self._present_keys([version_id])) == 1
 
1535
        return len(self._present_keys(self._version_ids_to_keys([version_id]))) == 1
 
1536
 
 
1537
    def _keys_to_version_ids(self, keys):
 
1538
        return tuple(key[0] for key in keys)
1520
1539
 
1521
1540
    def get_position(self, version_id):
1522
1541
        """Return data position and size of specified version."""
1537
1556
            return 'fulltext'
1538
1557
 
1539
1558
    def _get_node(self, version_id):
1540
 
        return list(self._get_entries([version_id]))[0]
 
1559
        return list(self._get_entries(self._version_ids_to_keys([version_id])))[0]
1541
1560
 
1542
1561
    def get_options(self, version_id):
1543
1562
        """Return a string represention options.
1551
1570
            options = [self._parent_compression(node[2][1])]
1552
1571
        if node[1][0] == 'N':
1553
1572
            options.append('no-eol')
1554
 
        return ','.join(options)
 
1573
        return options
1555
1574
 
1556
1575
    def get_parents(self, version_id):
1557
1576
        """Return parents of specified version ignoring ghosts."""
1563
1582
 
1564
1583
    def get_parents_with_ghosts(self, version_id):
1565
1584
        """Return parents of specified version with ghosts."""
1566
 
        nodes = list(self._get_entries([version_id], check_present=True))
 
1585
        nodes = list(self._get_entries(self._version_ids_to_keys([version_id]),
 
1586
            check_present=True))
1567
1587
        if not self._parents:
1568
1588
            return ()
1569
 
        return nodes[0][2][0]
 
1589
        return self._keys_to_version_ids(nodes[0][2][0])
1570
1590
 
1571
1591
    def check_versions_present(self, version_ids):
1572
1592
        """Check that all specified versions are present."""
1573
 
        version_ids = set(version_ids)
1574
 
        present = self._present_keys(version_ids)
1575
 
        missing = version_ids.difference(present)
 
1593
        keys = self._version_ids_to_keys(version_ids)
 
1594
        present = self._present_keys(keys)
 
1595
        missing = keys.difference(present)
1576
1596
        if missing:
1577
1597
            raise RevisionNotPresent(missing.pop(), self)
1578
1598
 
1599
1619
 
1600
1620
        keys = {}
1601
1621
        for (version_id, options, pos, size, parents) in versions:
 
1622
            # index keys are tuples:
 
1623
            key = (version_id, )
 
1624
            parents = tuple((parent, ) for parent in parents)
1602
1625
            if 'no-eol' in options:
1603
1626
                value = 'N'
1604
1627
            else:
1610
1633
            if self._parents:
1611
1634
                if self._deltas:
1612
1635
                    if 'line-delta' in options:
1613
 
                        node_refs = (tuple(parents), (parents[0],))
 
1636
                        node_refs = (parents, (parents[0],))
1614
1637
                    else:
1615
 
                        node_refs = (tuple(parents), ())
 
1638
                        node_refs = (parents, ())
1616
1639
                else:
1617
 
                    node_refs = (tuple(parents), )
 
1640
                    node_refs = (parents, )
1618
1641
            else:
1619
1642
                if parents:
1620
1643
                    raise KnitCorrupt(self, "attempt to add node with parents "
1621
1644
                        "in parentless index.")
1622
1645
                node_refs = ()
1623
 
            keys[version_id] = (value, node_refs)
 
1646
            keys[key] = (value, node_refs)
1624
1647
        present_nodes = self._get_entries(keys)
1625
1648
        for (key, value, node_refs) in present_nodes:
1626
1649
            if (value, node_refs) != keys[key]:
1636
1659
                result.append((key, value))
1637
1660
        self._add_callback(result)
1638
1661
        
 
1662
    def _version_ids_to_keys(self, version_ids):
 
1663
        return set((version_id, ) for version_id in version_ids)
 
1664
        
1639
1665
 
1640
1666
class _KnitData(_KnitComponentFile):
1641
1667
    """Contents of the knit data file"""