← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-07-25 02:47:25 UTC
  • mfrom: (2625.8.2 knits)
  • Revision ID: pqm@pqm.ubuntu.com-20070725024725-x592w4y7gdqxv81x
(robertc) Allow the adaption of Knits to external indices via KnitGraphIndex. (Robert Collins).

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
360
360
    def __init__(self, relpath, transport, file_mode=None, access_mode=None,
361
361
                 factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
362
362
                 create=False, create_parent_dir=False, delay_create=False,
363
 
                 dir_mode=None):
 
363
                 dir_mode=None, index=None):
364
364
        """Construct a knit at location specified by relpath.
365
365
        
366
366
        :param create: If not True, only open an existing knit.
369
369
            hash-prefixes that may not exist yet)
370
370
        :param delay_create: The calling code is aware that the knit won't 
371
371
            actually be created until the first data is stored.
 
372
        :param index: An index to use for the knit.
372
373
        """
373
374
        if deprecated_passed(basis_knit):
374
375
            warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
386
387
 
387
388
        self._max_delta_chain = 200
388
389
 
389
 
        self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
390
 
            access_mode, create=create, file_mode=file_mode,
391
 
            create_parent_dir=create_parent_dir, delay_create=delay_create,
392
 
            dir_mode=dir_mode)
 
390
        if index is None:
 
391
            self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
 
392
                access_mode, create=create, file_mode=file_mode,
 
393
                create_parent_dir=create_parent_dir, delay_create=delay_create,
 
394
                dir_mode=dir_mode)
 
395
        else:
 
396
            self._index = index
393
397
        self._data = _KnitData(transport, relpath + DATA_SUFFIX,
394
398
            access_mode, create=create and not len(self), file_mode=file_mode,
395
399
            create_parent_dir=create_parent_dir, delay_create=delay_create,
945
949
 
946
950
        pb.update('Walking content.', total, total)
947
951
        
 
952
    def iter_parents(self, version_ids):
 
953
        """Iterate through the parents for many version ids.
 
954
 
 
955
        :param version_ids: An iterable yielding version_ids.
 
956
        :return: An iterator that yields (version_id, parents). Requested 
 
957
            version_ids not present in the versioned file are simply skipped.
 
958
            The order is undefined, allowing for different optimisations in
 
959
            the underlying implementation.
 
960
        """
 
961
        version_ids = [osutils.safe_revision_id(version_id) for
 
962
            version_id in version_ids]
 
963
        return self._index.iter_parents(version_ids)
 
964
 
948
965
    def num_versions(self):
949
966
        """See VersionedFile.num_versions()."""
950
967
        return self._index.num_versions()
1172
1189
                    self._filename, self.HEADER, mode=self._file_mode)
1173
1190
 
1174
1191
    def get_graph(self):
 
1192
        """Return a list of the node:parents lists from this knit index."""
1175
1193
        return [(vid, idx[4]) for vid, idx in self._cache.iteritems()]
1176
1194
 
1177
1195
    def get_ancestry(self, versions, topo_sorted=True):
1214
1232
                graph[version] = parents
1215
1233
        return topo_sort(graph.items())
1216
1234
 
 
1235
    def iter_parents(self, version_ids):
 
1236
        """Iterate through the parents for many version ids.
 
1237
 
 
1238
        :param version_ids: An iterable yielding version_ids.
 
1239
        :return: An iterator that yields (version_id, parents). Requested 
 
1240
            version_ids not present in the versioned file are simply skipped.
 
1241
            The order is undefined, allowing for different optimisations in
 
1242
            the underlying implementation.
 
1243
        """
 
1244
        for version_id in version_ids:
 
1245
            try:
 
1246
                yield version_id, tuple(self.get_parents(version_id))
 
1247
            except KeyError:
 
1248
                pass
 
1249
 
1217
1250
    def num_versions(self):
1218
1251
        return len(self._history)
1219
1252
 
1220
1253
    __len__ = num_versions
1221
1254
 
1222
1255
    def get_versions(self):
 
1256
        """Get all the versions in the file. not topologically sorted."""
1223
1257
        return self._history
1224
1258
 
1225
 
    def idx_to_name(self, idx):
1226
 
        return self._history[idx]
1227
 
 
1228
 
    def lookup(self, version_id):
1229
 
        assert version_id in self._cache
1230
 
        return self._cache[version_id][5]
1231
 
 
1232
1259
    def _version_list_to_index(self, versions):
1233
1260
        result_list = []
1234
1261
        cache = self._cache
1304
1331
            return 'line-delta'
1305
1332
 
1306
1333
    def get_options(self, version_id):
 
1334
        """Return a string represention options.
 
1335
 
 
1336
        e.g. foo,bar
 
1337
        """
1307
1338
        return self._cache[version_id][1]
1308
1339
 
1309
1340
    def get_parents(self, version_id):
1323
1354
                raise RevisionNotPresent(version_id, self._filename)
1324
1355
 
1325
1356
 
 
1357
class KnitGraphIndex(object):
 
1358
    """A knit index that builds on GraphIndex."""
 
1359
 
 
1360
    def __init__(self, graph_index, deltas=False, parents=True, add_callback=None):
 
1361
        """Construct a KnitGraphIndex on a graph_index.
 
1362
 
 
1363
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
 
1364
        :param deltas: Allow delta-compressed records.
 
1365
        :param add_callback: If not None, allow additions to the index and call
 
1366
            this callback with a list of added GraphIndex nodes:
 
1367
            [(node, value, node_refs), ...]
 
1368
        :param parents: If True, record knits parents, if not do not record 
 
1369
            parents.
 
1370
        """
 
1371
        self._graph_index = graph_index
 
1372
        self._deltas = deltas
 
1373
        self._add_callback = add_callback
 
1374
        self._parents = parents
 
1375
        if deltas and not parents:
 
1376
            raise KnitCorrupt(self, "Cannot do delta compression without "
 
1377
                "parent tracking.")
 
1378
 
 
1379
    def _get_entries(self, version_ids, check_present=False):
 
1380
        """Get the entries for version_ids."""
 
1381
        version_ids = set(version_ids)
 
1382
        found_keys = set()
 
1383
        if self._parents:
 
1384
            for node in self._graph_index.iter_entries(version_ids):
 
1385
                yield node
 
1386
                found_keys.add(node[0])
 
1387
        else:
 
1388
            # adapt parentless index to the rest of the code.
 
1389
            for node in self._graph_index.iter_entries(version_ids):
 
1390
                yield node[0], node[1], ()
 
1391
                found_keys.add(node[0])
 
1392
        if check_present:
 
1393
            missing_keys = version_ids.difference(found_keys)
 
1394
            if missing_keys:
 
1395
                raise RevisionNotPresent(missing_keys.pop(), self)
 
1396
 
 
1397
    def _present_keys(self, version_ids):
 
1398
        return set([
 
1399
            node[0] for node in self._get_entries(version_ids)])
 
1400
 
 
1401
    def _parentless_ancestry(self, versions):
 
1402
        """Honour the get_ancestry API for parentless knit indices."""
 
1403
        present_keys = self._present_keys(versions)
 
1404
        missing = set(versions).difference(present_keys)
 
1405
        if missing:
 
1406
            raise RevisionNotPresent(missing.pop(), self)
 
1407
        return list(present_keys)
 
1408
 
 
1409
    def get_ancestry(self, versions, topo_sorted=True):
 
1410
        """See VersionedFile.get_ancestry."""
 
1411
        if not self._parents:
 
1412
            return self._parentless_ancestry(versions)
 
1413
        # XXX: This will do len(history) index calls - perhaps
 
1414
        # it should be altered to be a index core feature?
 
1415
        # get a graph of all the mentioned versions:
 
1416
        graph = {}
 
1417
        ghosts = set()
 
1418
        versions = set(versions)
 
1419
        pending = set(versions)
 
1420
        while pending:
 
1421
            # get all pending nodes
 
1422
            this_iteration = pending
 
1423
            new_nodes = self._get_entries(this_iteration)
 
1424
            pending = set()
 
1425
            for (key, value, node_refs) in new_nodes:
 
1426
                # dont ask for ghosties - otherwise
 
1427
                # we we can end up looping with pending
 
1428
                # being entirely ghosted.
 
1429
                graph[key] = [parent for parent in node_refs[0]
 
1430
                    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
        if versions.difference(graph):
 
1437
            raise RevisionNotPresent(versions.difference(graph).pop(), self)
 
1438
        if not topo_sorted:
 
1439
            return graph.keys()
 
1440
        return topo_sort(graph.items())
 
1441
 
 
1442
    def get_ancestry_with_ghosts(self, versions):
 
1443
        """See VersionedFile.get_ancestry."""
 
1444
        if not self._parents:
 
1445
            return self._parentless_ancestry(versions)
 
1446
        # XXX: This will do len(history) index calls - perhaps
 
1447
        # it should be altered to be a index core feature?
 
1448
        # get a graph of all the mentioned versions:
 
1449
        graph = {}
 
1450
        versions = set(versions)
 
1451
        pending = set(versions)
 
1452
        while pending:
 
1453
            # get all pending nodes
 
1454
            this_iteration = pending
 
1455
            new_nodes = self._get_entries(this_iteration)
 
1456
            pending = set()
 
1457
            for (key, value, node_refs) in new_nodes:
 
1458
                graph[key] = node_refs[0]
 
1459
                # queue parents 
 
1460
                pending.update(graph[key])
 
1461
            missing_versions = this_iteration.difference(graph)
 
1462
            missing_needed = versions.intersection(missing_versions)
 
1463
            if missing_needed:
 
1464
                raise RevisionNotPresent(missing_needed.pop(), self)
 
1465
            for missing_version in missing_versions:
 
1466
                # add a key, no parents
 
1467
                graph[missing_version] = []
 
1468
            # dont examine known nodes
 
1469
            pending.difference_update(graph)
 
1470
        return topo_sort(graph.items())
 
1471
 
 
1472
    def get_graph(self):
 
1473
        """Return a list of the node:parents lists from this knit index."""
 
1474
        if not self._parents:
 
1475
            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()]
 
1478
 
 
1479
    def iter_parents(self, version_ids):
 
1480
        """Iterate through the parents for many version ids.
 
1481
 
 
1482
        :param version_ids: An iterable yielding version_ids.
 
1483
        :return: An iterator that yields (version_id, parents). Requested 
 
1484
            version_ids not present in the versioned file are simply skipped.
 
1485
            The order is undefined, allowing for different optimisations in
 
1486
            the underlying implementation.
 
1487
        """
 
1488
        if self._parents:
 
1489
            all_nodes = set(self._get_entries(version_ids))
 
1490
            all_parents = set()
 
1491
            present_parents = set()
 
1492
            for node in all_nodes:
 
1493
                all_parents.update(node[2][0])
 
1494
                # any node we are querying must be present
 
1495
                present_parents.add(node[0])
 
1496
            unknown_parents = all_parents.difference(present_parents)
 
1497
            present_parents.update(self._present_keys(unknown_parents))
 
1498
            for node in all_nodes:
 
1499
                parents = []
 
1500
                for parent in node[2][0]:
 
1501
                    if parent in present_parents:
 
1502
                        parents.append(parent)
 
1503
                yield node[0], tuple(parents)
 
1504
        else:
 
1505
            for node in self._get_entries(version_ids):
 
1506
                yield node[0], ()
 
1507
 
 
1508
    def num_versions(self):
 
1509
        return len(list(self._graph_index.iter_all_entries()))
 
1510
 
 
1511
    __len__ = num_versions
 
1512
 
 
1513
    def get_versions(self):
 
1514
        """Get all the versions in the file. not topologically sorted."""
 
1515
        return [node[0] for node in self._graph_index.iter_all_entries()]
 
1516
    
 
1517
    def has_version(self, version_id):
 
1518
        """True if the version is in the index."""
 
1519
        return len(self._present_keys([version_id])) == 1
 
1520
 
 
1521
    def get_position(self, version_id):
 
1522
        """Return data position and size of specified version."""
 
1523
        bits = self._get_node(version_id)[1][1:].split(' ')
 
1524
        return int(bits[0]), int(bits[1])
 
1525
 
 
1526
    def get_method(self, version_id):
 
1527
        """Return compression method of specified version."""
 
1528
        if not self._deltas:
 
1529
            return 'fulltext'
 
1530
        return self._parent_compression(self._get_node(version_id)[2][1])
 
1531
 
 
1532
    def _parent_compression(self, reference_list):
 
1533
        # use the second reference list to decide if this is delta'd or not.
 
1534
        if len(reference_list):
 
1535
            return 'line-delta'
 
1536
        else:
 
1537
            return 'fulltext'
 
1538
 
 
1539
    def _get_node(self, version_id):
 
1540
        return list(self._get_entries([version_id]))[0]
 
1541
 
 
1542
    def get_options(self, version_id):
 
1543
        """Return a string represention options.
 
1544
 
 
1545
        e.g. foo,bar
 
1546
        """
 
1547
        node = self._get_node(version_id)
 
1548
        if not self._deltas:
 
1549
            options = ['fulltext']
 
1550
        else:
 
1551
            options = [self._parent_compression(node[2][1])]
 
1552
        if node[1][0] == 'N':
 
1553
            options.append('no-eol')
 
1554
        return ','.join(options)
 
1555
 
 
1556
    def get_parents(self, version_id):
 
1557
        """Return parents of specified version ignoring ghosts."""
 
1558
        parents = list(self.iter_parents([version_id]))
 
1559
        if not parents:
 
1560
            # missing key
 
1561
            raise errors.RevisionNotPresent(version_id, self)
 
1562
        return parents[0][1]
 
1563
 
 
1564
    def get_parents_with_ghosts(self, version_id):
 
1565
        """Return parents of specified version with ghosts."""
 
1566
        nodes = list(self._get_entries([version_id], check_present=True))
 
1567
        if not self._parents:
 
1568
            return ()
 
1569
        return nodes[0][2][0]
 
1570
 
 
1571
    def check_versions_present(self, version_ids):
 
1572
        """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)
 
1576
        if missing:
 
1577
            raise RevisionNotPresent(missing.pop(), self)
 
1578
 
 
1579
    def add_version(self, version_id, options, pos, size, parents):
 
1580
        """Add a version record to the index."""
 
1581
        return self.add_versions(((version_id, options, pos, size, parents),))
 
1582
 
 
1583
    def add_versions(self, versions):
 
1584
        """Add multiple versions to the index.
 
1585
        
 
1586
        This function does not insert data into the Immutable GraphIndex
 
1587
        backing the KnitGraphIndex, instead it prepares data for insertion by
 
1588
        the caller and checks that it is safe to insert then calls
 
1589
        self._add_callback with the prepared GraphIndex nodes.
 
1590
 
 
1591
        :param versions: a list of tuples:
 
1592
                         (version_id, options, pos, size, parents).
 
1593
        """
 
1594
        if not self._add_callback:
 
1595
            raise errors.ReadOnlyError(self)
 
1596
        # we hope there are no repositories with inconsistent parentage
 
1597
        # anymore.
 
1598
        # check for dups
 
1599
 
 
1600
        keys = {}
 
1601
        for (version_id, options, pos, size, parents) in versions:
 
1602
            if 'no-eol' in options:
 
1603
                value = 'N'
 
1604
            else:
 
1605
                value = ' '
 
1606
            value += "%d %d" % (pos, size)
 
1607
            if not self._deltas:
 
1608
                if 'line-delta' in options:
 
1609
                    raise KnitCorrupt(self, "attempt to add line-delta in non-delta knit")
 
1610
            if self._parents:
 
1611
                if self._deltas:
 
1612
                    if 'line-delta' in options:
 
1613
                        node_refs = (tuple(parents), (parents[0],))
 
1614
                    else:
 
1615
                        node_refs = (tuple(parents), ())
 
1616
                else:
 
1617
                    node_refs = (tuple(parents), )
 
1618
            else:
 
1619
                if parents:
 
1620
                    raise KnitCorrupt(self, "attempt to add node with parents "
 
1621
                        "in parentless index.")
 
1622
                node_refs = ()
 
1623
            keys[version_id] = (value, node_refs)
 
1624
        present_nodes = self._get_entries(keys)
 
1625
        for (key, value, node_refs) in present_nodes:
 
1626
            if (value, node_refs) != keys[key]:
 
1627
                raise KnitCorrupt(self, "inconsistent details in add_versions"
 
1628
                    ": %s %s" % ((value, node_refs), keys[key]))
 
1629
            del keys[key]
 
1630
        result = []
 
1631
        if self._parents:
 
1632
            for key, (value, node_refs) in keys.iteritems():
 
1633
                result.append((key, value, node_refs))
 
1634
        else:
 
1635
            for key, (value, node_refs) in keys.iteritems():
 
1636
                result.append((key, value))
 
1637
        self._add_callback(result)
 
1638
        
 
1639
 
1326
1640
class _KnitData(_KnitComponentFile):
1327
1641
    """Contents of the knit data file"""
1328
1642