/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 breezy/index.py

  • Committer: Jelmer Vernooij
  • Author(s): Richard Wilbur
  • Date: 2017-05-30 23:37:11 UTC
  • mto: This revision was merged to the branch mainline in revision 6645.
  • Revision ID: jelmer@jelmer.uk-20170530233711-r0m0qp8hpkqzpopw
https://launchpad.net/bugs/1537319
Fix order in which files are processed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/index.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007-2011 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
16
16
 
17
17
"""Indexing facilities."""
18
18
 
 
19
from __future__ import absolute_import
 
20
 
19
21
__all__ = [
20
22
    'CombinedGraphIndex',
21
23
    'GraphIndex',
25
27
    ]
26
28
 
27
29
from bisect import bisect_right
28
 
from cStringIO import StringIO
29
30
import re
30
31
import sys
31
32
 
32
 
from bzrlib.lazy_import import lazy_import
 
33
from .lazy_import import lazy_import
33
34
lazy_import(globals(), """
34
 
from bzrlib import trace
35
 
from bzrlib.bisect_multi import bisect_multi_bytes
36
 
from bzrlib.revision import NULL_REVISION
37
 
from bzrlib.trace import mutter
 
35
from breezy import (
 
36
    bisect_multi,
 
37
    revision as _mod_revision,
 
38
    trace,
 
39
    )
38
40
""")
39
 
from bzrlib import (
 
41
from . import (
40
42
    debug,
41
43
    errors,
42
44
    )
43
 
from bzrlib.static_tuple import StaticTuple
 
45
from .sixish import (
 
46
    BytesIO,
 
47
    )
 
48
from .static_tuple import StaticTuple
44
49
 
45
50
_HEADER_READV = (0, 200)
46
51
_OPTION_KEY_ELEMENTS = "key_elements="
69
74
class GraphIndexBuilder(object):
70
75
    """A builder that can build a GraphIndex.
71
76
 
72
 
    The resulting graph has the structure:
 
77
    The resulting graph has the structure::
73
78
 
74
 
    _SIGNATURE OPTIONS NODES NEWLINE
75
 
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
76
 
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
77
 
    NODES          := NODE*
78
 
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
79
 
    KEY            := Not-whitespace-utf8
80
 
    ABSENT         := 'a'
81
 
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
82
 
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
83
 
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
84
 
                              ; referenced key.
85
 
    VALUE          := no-newline-no-null-bytes
 
79
      _SIGNATURE OPTIONS NODES NEWLINE
 
80
      _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
 
81
      OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
 
82
      NODES          := NODE*
 
83
      NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
 
84
      KEY            := Not-whitespace-utf8
 
85
      ABSENT         := 'a'
 
86
      REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
 
87
      REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
 
88
      REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
 
89
                                ; referenced key.
 
90
      VALUE          := no-newline-no-null-bytes
86
91
    """
87
92
 
88
93
    def __init__(self, reference_lists=0, key_elements=1):
184
189
        :param value: The value associate with this key. Must not contain
185
190
            newlines or null characters.
186
191
        :return: (node_refs, absent_references)
187
 
            node_refs   basically a packed form of 'references' where all
188
 
                        iterables are tuples
189
 
            absent_references   reference keys that are not in self._nodes.
190
 
                                This may contain duplicates if the same key is
191
 
                                referenced in multiple lists.
 
192
        
 
193
            * node_refs: basically a packed form of 'references' where all
 
194
              iterables are tuples
 
195
            * absent_references: reference keys that are not in self._nodes.
 
196
              This may contain duplicates if the same key is referenced in
 
197
              multiple lists.
192
198
        """
193
199
        as_st = StaticTuple.from_sequence
194
200
        self._check_key(key)
219
225
        :param references: An iterable of iterables of keys. Each is a
220
226
            reference to another key.
221
227
        :param value: The value to associate with the key. It may be any
222
 
            bytes as long as it does not contain \0 or \n.
 
228
            bytes as long as it does not contain \\0 or \\n.
223
229
        """
224
230
        (node_refs,
225
231
         absent_references) = self._check_key_ref_value(key, references, value)
243
249
        """
244
250
        
245
251
    def finish(self):
 
252
        """Finish the index.
 
253
 
 
254
        :returns: cBytesIO holding the full context of the index as it 
 
255
        should be written to disk.
 
256
        """
246
257
        lines = [_SIGNATURE]
247
258
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
259
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
322
333
            lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
323
334
                '\t'.join(flattened_references), value))
324
335
        lines.append('\n')
325
 
        result = StringIO(''.join(lines))
 
336
        result = BytesIO(''.join(lines))
326
337
        if expected_bytes and len(result.getvalue()) != expected_bytes:
327
338
            raise errors.BzrError('Failed index creation. Internal error:'
328
339
                ' mismatched output length and expected length: %d %d' %
385
396
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
386
397
        """Open an index called name on transport.
387
398
 
388
 
        :param transport: A bzrlib.transport.Transport.
 
399
        :param transport: A breezy.transport.Transport.
389
400
        :param name: A path to provide to transport API calls.
390
401
        :param size: The size of the index in bytes. This is used for bisection
391
402
            logic to perform partial index reads. While the size could be
423
434
    def __eq__(self, other):
424
435
        """Equal when self and other were created with the same parameters."""
425
436
        return (
426
 
            type(self) == type(other) and
 
437
            isinstance(self, type(other)) and
427
438
            self._transport == other._transport and
428
439
            self._name == other._name and
429
440
            self._size == other._size)
444
455
            # We already did this
445
456
            return
446
457
        if 'index' in debug.debug_flags:
447
 
            mutter('Reading entire index %s', self._transport.abspath(self._name))
 
458
            trace.mutter('Reading entire index %s',
 
459
                          self._transport.abspath(self._name))
448
460
        if stream is None:
449
461
            stream = self._transport.get(self._name)
450
462
            if self._base_offset != 0:
451
463
                # This is wasteful, but it is better than dealing with
452
464
                # adjusting all the offsets, etc.
453
 
                stream = StringIO(stream.read()[self._base_offset:])
 
465
                stream = BytesIO(stream.read()[self._base_offset:])
454
466
        self._read_prefix(stream)
455
467
        self._expected_elements = 3 + self._key_length
456
468
        line_count = 0
462
474
        trailers = 0
463
475
        pos = stream.tell()
464
476
        lines = stream.read().split('\n')
 
477
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
465
478
        stream.close()
466
479
        del lines[-1]
467
480
        _, _, _, trailers = self._parse_lines(lines, pos)
670
683
        if self._nodes is not None:
671
684
            return self._iter_entries_from_total_buffer(keys)
672
685
        else:
673
 
            return (result[1] for result in bisect_multi_bytes(
 
686
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
674
687
                self._lookup_keys_via_location, self._size, keys))
675
688
 
676
689
    def iter_entries_prefix(self, keys):
737
750
                while dicts:
738
751
                    key_dict = dicts.pop(-1)
739
752
                    # can't be empty or would not exist
740
 
                    item, value = key_dict.iteritems().next()
741
 
                    if type(value) == dict:
 
753
                    item, value = next(key_dict.iteritems())
 
754
                    if isinstance(value, dict):
742
755
                        # push keys
743
756
                        dicts.extend(key_dict.itervalues())
744
757
                    else:
787
800
 
788
801
        :param location_keys: A list of location(byte offset), key tuples.
789
802
        :return: A list of (location_key, result) tuples as expected by
790
 
            bzrlib.bisect_multi.bisect_multi_bytes.
 
803
            breezy.bisect_multi.bisect_multi_bytes.
791
804
        """
792
805
        # Possible improvements:
793
806
        #  - only bisect lookup each key once
1217
1230
                # We read the whole range, most likely because the
1218
1231
                # Transport upcast our readv ranges into one long request
1219
1232
                # for enough total data to grab the whole index.
1220
 
                self._buffer_all(StringIO(data))
 
1233
                self._buffer_all(BytesIO(data))
1221
1234
                return
1222
1235
            if self._bisect_nodes is None:
1223
1236
                # this must be the start
1287
1300
    def get_parent_map(self, keys):
1288
1301
        """See graph.StackedParentsProvider.get_parent_map"""
1289
1302
        search_keys = set(keys)
1290
 
        if NULL_REVISION in search_keys:
1291
 
            search_keys.discard(NULL_REVISION)
1292
 
            found_parents = {NULL_REVISION:[]}
 
1303
        if _mod_revision.NULL_REVISION in search_keys:
 
1304
            search_keys.discard(_mod_revision.NULL_REVISION)
 
1305
            found_parents = {_mod_revision.NULL_REVISION:[]}
1293
1306
        else:
1294
1307
            found_parents = {}
1295
1308
        for index, key, value, refs in self.iter_entries(search_keys):
1296
1309
            parents = refs[0]
1297
1310
            if not parents:
1298
 
                parents = (NULL_REVISION,)
 
1311
                parents = (_mod_revision.NULL_REVISION,)
1299
1312
            found_parents[key] = parents
1300
1313
        return found_parents
1301
1314
 
1302
 
    has_key = _has_key_from_parent_map
 
1315
    __contains__ = _has_key_from_parent_map
1303
1316
 
1304
1317
    def insert_index(self, pos, index, name=None):
1305
1318
        """Insert a new index in the list of indices to query.
1332
1345
                            yield node
1333
1346
                            seen_keys.add(node[1])
1334
1347
                return
1335
 
            except errors.NoSuchFile:
1336
 
                self._reload_or_raise()
 
1348
            except errors.NoSuchFile as e:
 
1349
                if not self._try_reload(e):
 
1350
                    raise
1337
1351
 
1338
1352
    def iter_entries(self, keys):
1339
1353
        """Iterate over keys within the index.
1361
1375
                    if index_hit:
1362
1376
                        hit_indices.append(index)
1363
1377
                break
1364
 
            except errors.NoSuchFile:
1365
 
                self._reload_or_raise()
 
1378
            except errors.NoSuchFile as e:
 
1379
                if not self._try_reload(e):
 
1380
                    raise
1366
1381
        self._move_to_front(hit_indices)
1367
1382
 
1368
1383
    def iter_entries_prefix(self, keys):
1403
1418
                    if index_hit:
1404
1419
                        hit_indices.append(index)
1405
1420
                break
1406
 
            except errors.NoSuchFile:
1407
 
                self._reload_or_raise()
 
1421
            except errors.NoSuchFile as e:
 
1422
                if not self._try_reload(e):
 
1423
                    raise
1408
1424
        self._move_to_front(hit_indices)
1409
1425
 
1410
1426
    def _move_to_front(self, hit_indices):
1433
1449
        """
1434
1450
        indices_info = zip(self._index_names, self._indices)
1435
1451
        if 'index' in debug.debug_flags:
1436
 
            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
1437
 
                   indices_info, hit_indices)
 
1452
            indices_info = list(indices_info)
 
1453
            trace.mutter('CombinedGraphIndex reordering: currently %r, '
 
1454
                         'promoting %r', indices_info, hit_indices)
1438
1455
        hit_names = []
1439
1456
        unhit_names = []
1440
1457
        new_hit_indices = []
1457
1474
        self._indices = new_hit_indices + unhit_indices
1458
1475
        self._index_names = hit_names + unhit_names
1459
1476
        if 'index' in debug.debug_flags:
1460
 
            mutter('CombinedGraphIndex reordered: %r', self._indices)
 
1477
            trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
1461
1478
        return hit_names
1462
1479
 
1463
1480
    def _move_to_front_by_name(self, hit_names):
1548
1565
        while True:
1549
1566
            try:
1550
1567
                return sum((index.key_count() for index in self._indices), 0)
1551
 
            except errors.NoSuchFile:
1552
 
                self._reload_or_raise()
 
1568
            except errors.NoSuchFile as e:
 
1569
                if not self._try_reload(e):
 
1570
                    raise
1553
1571
 
1554
1572
    missing_keys = _missing_keys_from_parent_map
1555
1573
 
1556
 
    def _reload_or_raise(self):
 
1574
    def _try_reload(self, error):
1557
1575
        """We just got a NoSuchFile exception.
1558
1576
 
1559
1577
        Try to reload the indices, if it fails, just raise the current
1560
1578
        exception.
1561
1579
        """
1562
1580
        if self._reload_func is None:
1563
 
            raise
1564
 
        exc_type, exc_value, exc_traceback = sys.exc_info()
1565
 
        trace.mutter('Trying to reload after getting exception: %s',
1566
 
                     exc_value)
 
1581
            return False
 
1582
        trace.mutter('Trying to reload after getting exception: %s', error)
1567
1583
        if not self._reload_func():
1568
1584
            # We tried to reload, but nothing changed, so we fail anyway
1569
1585
            trace.mutter('_reload_func indicated nothing has changed.'
1570
1586
                         ' Raising original exception.')
1571
 
            raise exc_type, exc_value, exc_traceback
 
1587
            return False
 
1588
        return True
1572
1589
 
1573
1590
    def set_sibling_indices(self, sibling_combined_graph_indices):
1574
1591
        """Set the CombinedGraphIndex objects to reorder after reordering self.
1582
1599
                for index in self._indices:
1583
1600
                    index.validate()
1584
1601
                return
1585
 
            except errors.NoSuchFile:
1586
 
                self._reload_or_raise()
 
1602
            except errors.NoSuchFile as e:
 
1603
                if not self._try_reload(e):
 
1604
                    raise
1587
1605
 
1588
1606
 
1589
1607
class InMemoryGraphIndex(GraphIndexBuilder):
1708
1726
                while dicts:
1709
1727
                    key_dict = dicts.pop(-1)
1710
1728
                    # can't be empty or would not exist
1711
 
                    item, value = key_dict.iteritems().next()
1712
 
                    if type(value) == dict:
 
1729
                    item, value = next(key_dict.iteritems())
 
1730
                    if isinstance(value, dict):
1713
1731
                        # push keys
1714
1732
                        dicts.extend(key_dict.itervalues())
1715
1733
                    else: