/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: John Arbash Meinel
  • Date: 2009-11-07 00:28:26 UTC
  • mto: This revision was merged to the branch mainline in revision 4842.
  • Revision ID: john@arbash-meinel.com-20091107002826-umvwb3zl0yajo6rc
Use StaticTuple as part of the builder process.

Also use it in the pure python btree parser, mostly for consistency.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
93
93
        :param key_elements: The number of bytestrings in each key.
94
94
        """
95
95
        self.reference_lists = reference_lists
 
96
        self._keys = set()
96
97
        # A dict of {key: (absent, ref_lists, value)}
97
98
        self._nodes = {}
98
 
        # Keys that are referenced but not actually present in this index
99
 
        self._absent_keys = set()
100
99
        self._nodes_by_key = None
101
100
        self._key_length = key_elements
102
101
        self._optimize_for_size = False
166
165
            return
167
166
        key_dict = self._nodes_by_key
168
167
        if self.reference_lists:
169
 
            key_value = StaticTuple(key, value, node_refs)
 
168
            key_value = key, value, node_refs
170
169
        else:
171
 
            key_value = StaticTuple(key, value)
 
170
            key_value = key, value
172
171
        for subkey in key[:-1]:
173
172
            key_dict = key_dict.setdefault(subkey, {})
174
173
        key_dict[key[-1]] = key_value
205
204
                if reference not in self._nodes:
206
205
                    self._check_key(reference)
207
206
                    absent_references.append(reference)
208
 
            reference_list = as_st([as_st(ref).intern()
209
 
                                    for ref in reference_list])
210
 
            node_refs.append(reference_list)
 
207
            node_refs.append(as_st(reference_list))
211
208
        return as_st(node_refs), absent_references
212
209
 
213
210
    def add_node(self, key, value, references=()):
229
226
            # There may be duplicates, but I don't think it is worth worrying
230
227
            # about
231
228
            self._nodes[reference] = ('a', (), '')
232
 
        self._absent_keys.update(absent_references)
233
 
        self._absent_keys.discard(key)
234
229
        self._nodes[key] = ('', node_refs, value)
 
230
        self._keys.add(key)
235
231
        if self._nodes_by_key is not None and self._key_length > 1:
236
232
            self._update_nodes_by_key(key, value, node_refs)
237
233
 
246
242
        lines = [_SIGNATURE]
247
243
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
244
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
249
 
        key_count = len(self._nodes) - len(self._absent_keys)
250
 
        lines.append(_OPTION_LEN + str(key_count) + '\n')
 
245
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
251
246
        prefix_length = sum(len(x) for x in lines)
252
247
        # references are byte offsets. To avoid having to do nasty
253
248
        # polynomial work to resolve offsets (references to later in the
382
377
    suitable for production use. :XXX
383
378
    """
384
379
 
385
 
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
 
380
    def __init__(self, transport, name, size, unlimited_cache=False):
386
381
        """Open an index called name on transport.
387
382
 
388
383
        :param transport: A bzrlib.transport.Transport.
394
389
            avoided by having it supplied. If size is None, then bisection
395
390
            support will be disabled and accessing the index will just stream
396
391
            all the data.
397
 
        :param offset: Instead of starting the index data at offset 0, start it
398
 
            at an arbitrary offset.
399
392
        """
400
393
        self._transport = transport
401
394
        self._name = name
418
411
        self._size = size
419
412
        # The number of bytes we've read so far in trying to process this file
420
413
        self._bytes_read = 0
421
 
        self._base_offset = offset
422
414
 
423
415
    def __eq__(self, other):
424
416
        """Equal when self and other were created with the same parameters."""
447
439
            mutter('Reading entire index %s', self._transport.abspath(self._name))
448
440
        if stream is None:
449
441
            stream = self._transport.get(self._name)
450
 
            if self._base_offset != 0:
451
 
                # This is wasteful, but it is better than dealing with
452
 
                # adjusting all the offsets, etc.
453
 
                stream = StringIO(stream.read()[self._base_offset:])
454
442
        self._read_prefix(stream)
455
443
        self._expected_elements = 3 + self._key_length
456
444
        line_count = 0
462
450
        trailers = 0
463
451
        pos = stream.tell()
464
452
        lines = stream.read().split('\n')
465
 
        stream.close()
466
453
        del lines[-1]
467
454
        _, _, _, trailers = self._parse_lines(lines, pos)
468
455
        for key, absent, references, value in self._keys_by_offset.itervalues():
475
462
                node_value = value
476
463
            self._nodes[key] = node_value
477
464
        # cache the keys for quick set intersections
 
465
        self._keys = set(self._nodes)
478
466
        if trailers != 1:
479
467
            # there must be one line - the empty trailer line.
480
468
            raise errors.BadIndexData(self)
495
483
            raise ValueError('No ref list %d, index has %d ref lists'
496
484
                % (ref_list_num, self.node_ref_lists))
497
485
        refs = set()
498
 
        nodes = self._nodes
499
 
        for key, (value, ref_lists) in nodes.iteritems():
 
486
        for key, (value, ref_lists) in self._nodes.iteritems():
500
487
            ref_list = ref_lists[ref_list_num]
501
 
            refs.update([ref for ref in ref_list if ref not in nodes])
502
 
        return refs
 
488
            refs.update(ref_list)
 
489
        return refs - self._keys
503
490
 
504
491
    def _get_nodes_by_key(self):
505
492
        if self._nodes_by_key is None:
632
619
 
633
620
    def _iter_entries_from_total_buffer(self, keys):
634
621
        """Iterate over keys when the entire index is parsed."""
635
 
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
636
 
        #       .intersection() here
637
 
        nodes = self._nodes
638
 
        keys = [key for key in keys if key in nodes]
 
622
        keys = keys.intersection(self._keys)
639
623
        if self.node_ref_lists:
640
624
            for key in keys:
641
 
                value, node_refs = nodes[key]
 
625
                value, node_refs = self._nodes[key]
642
626
                yield self, key, value, node_refs
643
627
        else:
644
628
            for key in keys:
645
 
                yield self, key, nodes[key]
 
629
                yield self, key, self._nodes[key]
646
630
 
647
631
    def iter_entries(self, keys):
648
632
        """Iterate over keys within the index.
1197
1181
            self._buffer_all()
1198
1182
            return
1199
1183
 
1200
 
        base_offset = self._base_offset
1201
 
        if base_offset != 0:
1202
 
            # Rewrite the ranges for the offset
1203
 
            readv_ranges = [(start+base_offset, size)
1204
 
                            for start, size in readv_ranges]
1205
1184
        readv_data = self._transport.readv(self._name, readv_ranges, True,
1206
 
            self._size + self._base_offset)
 
1185
            self._size)
1207
1186
        # parse
1208
1187
        for offset, data in readv_data:
1209
 
            offset -= base_offset
1210
1188
            self._bytes_read += len(data)
1211
 
            if offset < 0:
1212
 
                # transport.readv() expanded to extra data which isn't part of
1213
 
                # this index
1214
 
                data = data[-offset:]
1215
 
                offset = 0
1216
1189
            if offset == 0 and len(data) == self._size:
1217
1190
                # We read the whole range, most likely because the
1218
1191
                # Transport upcast our readv ranges into one long request
1245
1218
    static data.
1246
1219
 
1247
1220
    Queries against the combined index will be made against the first index,
1248
 
    and then the second and so on. The order of indices can thus influence
 
1221
    and then the second and so on. The order of index's can thus influence
1249
1222
    performance significantly. For example, if one index is on local disk and a
1250
1223
    second on a remote server, the local disk index should be before the other
1251
1224
    in the index list.
1252
 
    
1253
 
    Also, queries tend to need results from the same indices as previous
1254
 
    queries.  So the indices will be reordered after every query to put the
1255
 
    indices that had the result(s) of that query first (while otherwise
1256
 
    preserving the relative ordering).
1257
1225
    """
1258
1226
 
1259
1227
    def __init__(self, indices, reload_func=None):
1266
1234
        """
1267
1235
        self._indices = indices
1268
1236
        self._reload_func = reload_func
1269
 
        # Sibling indices are other CombinedGraphIndex that we should call
1270
 
        # _move_to_front_by_name on when we auto-reorder ourself.
1271
 
        self._sibling_indices = []
1272
 
        # A list of names that corresponds to the instances in self._indices,
1273
 
        # so _index_names[0] is always the name for _indices[0], etc.  Sibling
1274
 
        # indices must all use the same set of names as each other.
1275
 
        self._index_names = [None] * len(self._indices)
1276
1237
 
1277
1238
    def __repr__(self):
1278
1239
        return "%s(%s)" % (
1301
1262
 
1302
1263
    has_key = _has_key_from_parent_map
1303
1264
 
1304
 
    def insert_index(self, pos, index, name=None):
 
1265
    def insert_index(self, pos, index):
1305
1266
        """Insert a new index in the list of indices to query.
1306
1267
 
1307
1268
        :param pos: The position to insert the index.
1308
1269
        :param index: The index to insert.
1309
 
        :param name: a name for this index, e.g. a pack name.  These names can
1310
 
            be used to reflect index reorderings to related CombinedGraphIndex
1311
 
            instances that use the same names.  (see set_sibling_indices)
1312
1270
        """
1313
1271
        self._indices.insert(pos, index)
1314
 
        self._index_names.insert(pos, name)
1315
1272
 
1316
1273
    def iter_all_entries(self):
1317
1274
        """Iterate over all keys within the index
1342
1299
        value and are only reported once.
1343
1300
 
1344
1301
        :param keys: An iterable providing the keys to be retrieved.
1345
 
        :return: An iterable of (index, key, reference_lists, value). There is
1346
 
            no defined order for the result iteration - it will be in the most
 
1302
        :return: An iterable of (index, key, reference_lists, value). There is no
 
1303
            defined order for the result iteration - it will be in the most
1347
1304
            efficient order for the index.
1348
1305
        """
1349
1306
        keys = set(keys)
1350
 
        hit_indices = []
1351
1307
        while True:
1352
1308
            try:
1353
1309
                for index in self._indices:
1354
1310
                    if not keys:
1355
 
                        break
1356
 
                    index_hit = False
 
1311
                        return
1357
1312
                    for node in index.iter_entries(keys):
1358
1313
                        keys.remove(node[1])
1359
1314
                        yield node
1360
 
                        index_hit = True
1361
 
                    if index_hit:
1362
 
                        hit_indices.append(index)
1363
 
                break
 
1315
                return
1364
1316
            except errors.NoSuchFile:
1365
1317
                self._reload_or_raise()
1366
 
        self._move_to_front(hit_indices)
1367
1318
 
1368
1319
    def iter_entries_prefix(self, keys):
1369
1320
        """Iterate over keys within the index using prefix matching.
1389
1340
        if not keys:
1390
1341
            return
1391
1342
        seen_keys = set()
1392
 
        hit_indices = []
1393
1343
        while True:
1394
1344
            try:
1395
1345
                for index in self._indices:
1396
 
                    index_hit = False
1397
1346
                    for node in index.iter_entries_prefix(keys):
1398
1347
                        if node[1] in seen_keys:
1399
1348
                            continue
1400
1349
                        seen_keys.add(node[1])
1401
1350
                        yield node
1402
 
                        index_hit = True
1403
 
                    if index_hit:
1404
 
                        hit_indices.append(index)
1405
 
                break
 
1351
                return
1406
1352
            except errors.NoSuchFile:
1407
1353
                self._reload_or_raise()
1408
 
        self._move_to_front(hit_indices)
1409
 
 
1410
 
    def _move_to_front(self, hit_indices):
1411
 
        """Rearrange self._indices so that hit_indices are first.
1412
 
 
1413
 
        Order is maintained as much as possible, e.g. the first unhit index
1414
 
        will be the first index in _indices after the hit_indices, and the
1415
 
        hit_indices will be present in exactly the order they are passed to
1416
 
        _move_to_front.
1417
 
 
1418
 
        _move_to_front propagates to all objects in self._sibling_indices by
1419
 
        calling _move_to_front_by_name.
1420
 
        """
1421
 
        if self._indices[:len(hit_indices)] == hit_indices:
1422
 
            # The 'hit_indices' are already at the front (and in the same
1423
 
            # order), no need to re-order
1424
 
            return
1425
 
        hit_names = self._move_to_front_by_index(hit_indices)
1426
 
        for sibling_idx in self._sibling_indices:
1427
 
            sibling_idx._move_to_front_by_name(hit_names)
1428
 
 
1429
 
    def _move_to_front_by_index(self, hit_indices):
1430
 
        """Core logic for _move_to_front.
1431
 
        
1432
 
        Returns a list of names corresponding to the hit_indices param.
1433
 
        """
1434
 
        indices_info = zip(self._index_names, self._indices)
1435
 
        if 'index' in debug.debug_flags:
1436
 
            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
1437
 
                   indices_info, hit_indices)
1438
 
        hit_names = []
1439
 
        unhit_names = []
1440
 
        new_hit_indices = []
1441
 
        unhit_indices = []
1442
 
 
1443
 
        for offset, (name, idx) in enumerate(indices_info):
1444
 
            if idx in hit_indices:
1445
 
                hit_names.append(name)
1446
 
                new_hit_indices.append(idx)
1447
 
                if len(new_hit_indices) == len(hit_indices):
1448
 
                    # We've found all of the hit entries, everything else is
1449
 
                    # unhit
1450
 
                    unhit_names.extend(self._index_names[offset+1:])
1451
 
                    unhit_indices.extend(self._indices[offset+1:])
1452
 
                    break
1453
 
            else:
1454
 
                unhit_names.append(name)
1455
 
                unhit_indices.append(idx)
1456
 
 
1457
 
        self._indices = new_hit_indices + unhit_indices
1458
 
        self._index_names = hit_names + unhit_names
1459
 
        if 'index' in debug.debug_flags:
1460
 
            mutter('CombinedGraphIndex reordered: %r', self._indices)
1461
 
        return hit_names
1462
 
 
1463
 
    def _move_to_front_by_name(self, hit_names):
1464
 
        """Moves indices named by 'hit_names' to front of the search order, as
1465
 
        described in _move_to_front.
1466
 
        """
1467
 
        # Translate names to index instances, and then call
1468
 
        # _move_to_front_by_index.
1469
 
        indices_info = zip(self._index_names, self._indices)
1470
 
        hit_indices = []
1471
 
        for name, idx in indices_info:
1472
 
            if name in hit_names:
1473
 
                hit_indices.append(idx)
1474
 
        self._move_to_front_by_index(hit_indices)
1475
1354
 
1476
1355
    def find_ancestry(self, keys, ref_list_num):
1477
1356
        """Find the complete ancestry for the given set of keys.
1484
1363
            we care about.
1485
1364
        :return: (parent_map, missing_keys)
1486
1365
        """
1487
 
        # XXX: make this call _move_to_front?
1488
1366
        missing_keys = set()
1489
1367
        parent_map = {}
1490
1368
        keys_to_lookup = set(keys)
1570
1448
                         ' Raising original exception.')
1571
1449
            raise exc_type, exc_value, exc_traceback
1572
1450
 
1573
 
    def set_sibling_indices(self, sibling_combined_graph_indices):
1574
 
        """Set the CombinedGraphIndex objects to reorder after reordering self.
1575
 
        """
1576
 
        self._sibling_indices = sibling_combined_graph_indices
1577
 
 
1578
1451
    def validate(self):
1579
1452
        """Validate that everything in the index can be accessed."""
1580
1453
        while True:
1633
1506
            defined order for the result iteration - it will be in the most
1634
1507
            efficient order for the index (keys iteration order in this case).
1635
1508
        """
1636
 
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
1637
 
        #       aren't using set().intersection() here
1638
 
        nodes = self._nodes
1639
 
        keys = [key for key in keys if key in nodes]
 
1509
        keys = set(keys)
1640
1510
        if self.reference_lists:
1641
 
            for key in keys:
1642
 
                node = nodes[key]
 
1511
            for key in keys.intersection(self._keys):
 
1512
                node = self._nodes[key]
1643
1513
                if not node[0]:
1644
1514
                    yield self, key, node[2], node[1]
1645
1515
        else:
1646
 
            for key in keys:
1647
 
                node = nodes[key]
 
1516
            for key in keys.intersection(self._keys):
 
1517
                node = self._nodes[key]
1648
1518
                if not node[0]:
1649
1519
                    yield self, key, node[2]
1650
1520
 
1724
1594
 
1725
1595
        For InMemoryGraphIndex the estimate is exact.
1726
1596
        """
1727
 
        return len(self._nodes) - len(self._absent_keys)
 
1597
        return len(self._keys)
1728
1598
 
1729
1599
    def validate(self):
1730
1600
        """In memory index's have no known corruption at the moment."""