← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Robert Collins
  • Date: 2007-07-12 14:48:09 UTC
  • mto: (2592.5.3 pack-repository)
  • mto: This revision was merged to the branch mainline in revision 2624.
  • Revision ID: robertc@robertcollins.net-20070712144809-3cnuwhg0k86uo3qq
Iterating no keys should work too.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
17
17
"""Indexing facilities."""
18
18
 
19
19
from cStringIO import StringIO
20
 
import re
21
20
 
22
21
from bzrlib import errors
23
22
 
25
24
_SIGNATURE = "Bazaar Graph Index 1\n"
26
25
 
27
26
 
28
 
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
29
 
_newline_null_re = re.compile('[\n\0]')
30
 
 
31
 
 
32
27
class GraphIndexBuilder(object):
33
 
    """A builder that can build a GraphIndex.
34
 
    
35
 
    The resulting graph has the structure:
36
 
    
37
 
    _SIGNATURE OPTIONS NODES NEWLINE
38
 
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
39
 
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
40
 
    NODES          := NODE*
41
 
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
42
 
    KEY            := Not-whitespace-utf8
43
 
    ABSENT         := 'a'
44
 
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
45
 
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
46
 
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
47
 
                              ; referenced key.
48
 
    VALUE          := no-newline-no-null-bytes
49
 
    """
 
28
    """A builder that can build a GraphIndex."""
50
29
 
51
30
    def __init__(self, reference_lists=0):
52
31
        """Create a GraphIndex builder.
55
34
            entry.
56
35
        """
57
36
        self.reference_lists = reference_lists
58
 
        self._nodes = {}
59
 
 
60
 
    def add_node(self, key, references, value):
61
 
        """Add a node to the index.
62
 
 
63
 
        :param key: The key. keys must be whitespace free utf8.
64
 
        :param references: An iterable of iterables of keys. Each is a
65
 
            reference to another key.
66
 
        :param value: The value to associate with the key. It may be any
67
 
            bytes as long as it does not contain \0 or \n.
68
 
        """
69
 
        if not key or _whitespace_re.search(key) is not None:
70
 
            raise errors.BadIndexKey(key)
71
 
        if _newline_null_re.search(value) is not None:
72
 
            raise errors.BadIndexValue(value)
73
 
        if len(references) != self.reference_lists:
74
 
            raise errors.BadIndexValue(references)
75
 
        for reference_list in references:
76
 
            for reference in reference_list:
77
 
                if _whitespace_re.search(reference) is not None:
78
 
                    raise errors.BadIndexKey(reference)
79
 
        if key in self._nodes:
80
 
            raise errors.BadIndexDuplicateKey(key, self)
81
 
        self._nodes[key] = (references, value)
82
37
 
83
38
    def finish(self):
84
39
        lines = [_SIGNATURE]
85
40
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
86
 
        for key, (references, value) in sorted(self._nodes.items(),reverse=True):
87
 
            flattened_references = []
88
 
            for ref_list in references:
89
 
                flattened_references.append('')
90
 
            lines.append("%s\0\0%s\0%s\n" % (key,
91
 
                '\t'.join(flattened_references), value))
92
41
        lines.append('\n')
93
42
        return StringIO(''.join(lines))
94
43
 
95
44
 
96
45
class GraphIndex(object):
97
46
    """An index for data with embedded graphs.
98
 
 
99
 
    The index maps keys to a list of key reference lists, and a value.
100
 
    Each node has the same number of key reference lists. Each key reference
101
 
    list can be empty or an arbitrary length. The value is an opaque NULL
102
 
    terminated string without any newlines.
 
47
    
103
48
    """
104
49
 
105
50
    def __init__(self, transport, name):
144
89
        signature = stream.read(len(self._signature()))
145
90
        if not signature == self._signature():
146
91
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
147
 
        options_line = stream.readline()
148
 
        if not options_line.startswith(_OPTION_NODE_REFS):
149
 
            raise errors.BadIndexOptions(self)
150
 
        try:
151
 
            node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
152
 
        except ValueError:
153
 
            raise errors.BadIndexOptions(self)
154
 
        line_count = 0
155
 
        for line in stream.readlines():
156
 
            # validate the line
157
 
            line_count += 1
158
 
        if line_count < 1:
159
 
            # there must be one line - the empty trailer line.
160
 
            raise errors.BadIndexData(self)