← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_dirstate_helpers_py.py

  • Committer: Martin Pool
  • Date: 2005-08-24 08:59:32 UTC
  • Revision ID: mbp@sourcefrog.net-20050824085932-c61f1f1f1c930e13
- Add a simple UIFactory 

  The idea of this is to let a client of bzrlib set some 
  policy about how output is displayed.

  In this revision all that's done is that progress bars
  are constructed by a policy established by the application
  rather than being randomly constructed in the library 
  or passed down the calls.  This avoids progress bars
  popping up while running the test suite and cleans up
  some code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_dirstate_helpers_py.py
1
 
# Copyright (C) 2007, 2008 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
"""Python implementations of Dirstate Helper functions."""
18
 
 
19
 
import os
20
 
 
21
 
# We cannot import the dirstate module, because it loads this module
22
 
# All we really need is the IN_MEMORY_MODIFIED constant
23
 
from bzrlib import errors
24
 
from bzrlib.dirstate import DirState
25
 
 
26
 
 
27
 
def _bisect_path_left(paths, path):
28
 
    """Return the index where to insert path into paths.
29
 
 
30
 
    This uses the dirblock sorting. So all children in a directory come before
31
 
    the children of children. For example::
32
 
 
33
 
        a/
34
 
          b/
35
 
            c
36
 
          d/
37
 
            e
38
 
          b-c
39
 
          d-e
40
 
        a-a
41
 
        a=c
42
 
 
43
 
    Will be sorted as::
44
 
 
45
 
        a
46
 
        a-a
47
 
        a=c
48
 
        a/b
49
 
        a/b-c
50
 
        a/d
51
 
        a/d-e
52
 
        a/b/c
53
 
        a/d/e
54
 
 
55
 
    :param paths: A list of paths to search through
56
 
    :param path: A single path to insert
57
 
    :return: An offset where 'path' can be inserted.
58
 
    :seealso: bisect.bisect_left
59
 
    """
60
 
    hi = len(paths)
61
 
    lo = 0
62
 
    while lo < hi:
63
 
        mid = (lo + hi) // 2
64
 
        # Grab the dirname for the current dirblock
65
 
        cur = paths[mid]
66
 
        if _cmp_path_by_dirblock(cur, path) < 0:
67
 
            lo = mid + 1
68
 
        else:
69
 
            hi = mid
70
 
    return lo
71
 
 
72
 
 
73
 
def _bisect_path_right(paths, path):
74
 
    """Return the index where to insert path into paths.
75
 
 
76
 
    This uses a path-wise comparison so we get::
77
 
        a
78
 
        a-b
79
 
        a=b
80
 
        a/b
81
 
    Rather than::
82
 
        a
83
 
        a-b
84
 
        a/b
85
 
        a=b
86
 
    :param paths: A list of paths to search through
87
 
    :param path: A single path to insert
88
 
    :return: An offset where 'path' can be inserted.
89
 
    :seealso: bisect.bisect_right
90
 
    """
91
 
    hi = len(paths)
92
 
    lo = 0
93
 
    while lo < hi:
94
 
        mid = (lo+hi)//2
95
 
        # Grab the dirname for the current dirblock
96
 
        cur = paths[mid]
97
 
        if _cmp_path_by_dirblock(path, cur) < 0:
98
 
            hi = mid
99
 
        else:
100
 
            lo = mid + 1
101
 
    return lo
102
 
 
103
 
 
104
 
def bisect_dirblock(dirblocks, dirname, lo=0, hi=None, cache={}):
105
 
    """Return the index where to insert dirname into the dirblocks.
106
 
 
107
 
    The return value idx is such that all directories blocks in dirblock[:idx]
108
 
    have names < dirname, and all blocks in dirblock[idx:] have names >=
109
 
    dirname.
110
 
 
111
 
    Optional args lo (default 0) and hi (default len(dirblocks)) bound the
112
 
    slice of a to be searched.
113
 
    """
114
 
    if hi is None:
115
 
        hi = len(dirblocks)
116
 
    try:
117
 
        dirname_split = cache[dirname]
118
 
    except KeyError:
119
 
        dirname_split = dirname.split('/')
120
 
        cache[dirname] = dirname_split
121
 
    while lo < hi:
122
 
        mid = (lo + hi) // 2
123
 
        # Grab the dirname for the current dirblock
124
 
        cur = dirblocks[mid][0]
125
 
        try:
126
 
            cur_split = cache[cur]
127
 
        except KeyError:
128
 
            cur_split = cur.split('/')
129
 
            cache[cur] = cur_split
130
 
        if cur_split < dirname_split: lo = mid + 1
131
 
        else: hi = mid
132
 
    return lo
133
 
 
134
 
 
135
 
def cmp_by_dirs(path1, path2):
136
 
    """Compare two paths directory by directory.
137
 
 
138
 
    This is equivalent to doing::
139
 
 
140
 
       cmp(path1.split('/'), path2.split('/'))
141
 
 
142
 
    The idea is that you should compare path components separately. This
143
 
    differs from plain ``cmp(path1, path2)`` for paths like ``'a-b'`` and
144
 
    ``a/b``. "a-b" comes after "a" but would come before "a/b" lexically.
145
 
 
146
 
    :param path1: first path
147
 
    :param path2: second path
148
 
    :return: negative number if ``path1`` comes first,
149
 
        0 if paths are equal,
150
 
        and positive number if ``path2`` sorts first
151
 
    """
152
 
    if not isinstance(path1, str):
153
 
        raise TypeError("'path1' must be a plain string, not %s: %r"
154
 
                        % (type(path1), path1))
155
 
    if not isinstance(path2, str):
156
 
        raise TypeError("'path2' must be a plain string, not %s: %r"
157
 
                        % (type(path2), path2))
158
 
    return cmp(path1.split('/'), path2.split('/'))
159
 
 
160
 
 
161
 
def _cmp_path_by_dirblock(path1, path2):
162
 
    """Compare two paths based on what directory they are in.
163
 
 
164
 
    This generates a sort order, such that all children of a directory are
165
 
    sorted together, and grandchildren are in the same order as the
166
 
    children appear. But all grandchildren come after all children.
167
 
 
168
 
    :param path1: first path
169
 
    :param path2: the second path
170
 
    :return: negative number if ``path1`` comes first,
171
 
        0 if paths are equal
172
 
        and a positive number if ``path2`` sorts first
173
 
    """
174
 
    if not isinstance(path1, str):
175
 
        raise TypeError("'path1' must be a plain string, not %s: %r"
176
 
                        % (type(path1), path1))
177
 
    if not isinstance(path2, str):
178
 
        raise TypeError("'path2' must be a plain string, not %s: %r"
179
 
                        % (type(path2), path2))
180
 
    dirname1, basename1 = os.path.split(path1)
181
 
    key1 = (dirname1.split('/'), basename1)
182
 
    dirname2, basename2 = os.path.split(path2)
183
 
    key2 = (dirname2.split('/'), basename2)
184
 
    return cmp(key1, key2)
185
 
 
186
 
 
187
 
def _read_dirblocks(state):
188
 
    """Read in the dirblocks for the given DirState object.
189
 
 
190
 
    This is tightly bound to the DirState internal representation. It should be
191
 
    thought of as a member function, which is only separated out so that we can
192
 
    re-write it in pyrex.
193
 
 
194
 
    :param state: A DirState object.
195
 
    :return: None
196
 
    """
197
 
    state._state_file.seek(state._end_of_header)
198
 
    text = state._state_file.read()
199
 
    # TODO: check the crc checksums. crc_measured = zlib.crc32(text)
200
 
 
201
 
    fields = text.split('\0')
202
 
    # Remove the last blank entry
203
 
    trailing = fields.pop()
204
 
    if trailing != '':
205
 
        raise errors.DirstateCorrupt(state,
206
 
            'trailing garbage: %r' % (trailing,))
207
 
    # consider turning fields into a tuple.
208
 
 
209
 
    # skip the first field which is the trailing null from the header.
210
 
    cur = 1
211
 
    # Each line now has an extra '\n' field which is not used
212
 
    # so we just skip over it
213
 
    # entry size:
214
 
    #  3 fields for the key
215
 
    #  + number of fields per tree_data (5) * tree count
216
 
    #  + newline
217
 
    num_present_parents = state._num_present_parents()
218
 
    tree_count = 1 + num_present_parents
219
 
    entry_size = state._fields_per_entry()
220
 
    expected_field_count = entry_size * state._num_entries
221
 
    field_count = len(fields)
222
 
    # this checks our adjustment, and also catches file too short.
223
 
    if field_count - cur != expected_field_count:
224
 
        raise errors.DirstateCorrupt(state,
225
 
            'field count incorrect %s != %s, entry_size=%s, '\
226
 
            'num_entries=%s fields=%r' % (
227
 
            field_count - cur, expected_field_count, entry_size,
228
 
            state._num_entries, fields))
229
 
 
230
 
    if num_present_parents == 1:
231
 
        # Bind external functions to local names
232
 
        _int = int
233
 
        # We access all fields in order, so we can just iterate over
234
 
        # them. Grab an straight iterator over the fields. (We use an
235
 
        # iterator because we don't want to do a lot of additions, nor
236
 
        # do we want to do a lot of slicing)
237
 
        next = iter(fields).next
238
 
        # Move the iterator to the current position
239
 
        for x in xrange(cur):
240
 
            next()
241
 
        # The two blocks here are deliberate: the root block and the
242
 
        # contents-of-root block.
243
 
        state._dirblocks = [('', []), ('', [])]
244
 
        current_block = state._dirblocks[0][1]
245
 
        current_dirname = ''
246
 
        append_entry = current_block.append
247
 
        for count in xrange(state._num_entries):
248
 
            dirname = next()
249
 
            name = next()
250
 
            file_id = next()
251
 
            if dirname != current_dirname:
252
 
                # new block - different dirname
253
 
                current_block = []
254
 
                current_dirname = dirname
255
 
                state._dirblocks.append((current_dirname, current_block))
256
 
                append_entry = current_block.append
257
 
            # we know current_dirname == dirname, so re-use it to avoid
258
 
            # creating new strings
259
 
            entry = ((current_dirname, name, file_id),
260
 
                     [(# Current Tree
261
 
                         next(),                # minikind
262
 
                         next(),                # fingerprint
263
 
                         _int(next()),          # size
264
 
                         next() == 'y',         # executable
265
 
                         next(),                # packed_stat or revision_id
266
 
                     ),
267
 
                     ( # Parent 1
268
 
                         next(),                # minikind
269
 
                         next(),                # fingerprint
270
 
                         _int(next()),          # size
271
 
                         next() == 'y',         # executable
272
 
                         next(),                # packed_stat or revision_id
273
 
                     ),
274
 
                     ])
275
 
            trailing = next()
276
 
            if trailing != '\n':
277
 
                raise ValueError("trailing garbage in dirstate: %r" % trailing)
278
 
            # append the entry to the current block
279
 
            append_entry(entry)
280
 
        state._split_root_dirblock_into_contents()
281
 
    else:
282
 
        fields_to_entry = state._get_fields_to_entry()
283
 
        entries = [fields_to_entry(fields[pos:pos+entry_size])
284
 
                   for pos in xrange(cur, field_count, entry_size)]
285
 
        state._entries_to_current_state(entries)
286
 
    # To convert from format 2  => format 3
287
 
    # state._dirblocks = sorted(state._dirblocks,
288
 
    #                          key=lambda blk:blk[0].split('/'))
289
 
    # To convert from format 3 => format 2
290
 
    # state._dirblocks = sorted(state._dirblocks)
291
 
    state._dirblock_state = DirState.IN_MEMORY_UNMODIFIED