1
# Copyright (C) 2006, 2007 Canonical Ltd
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
"""DirState objects record the state of a directory and its bzr metadata.
19
Pseduo EBNF grammar for the disk format:
20
MINIKIND = "f" | "d" | "l";
23
WHOLE NUMBER = {digit}, digit;
25
dirstate format = header line, full checksum, row count, parent details,
27
header line = "#bazaar dirstate flat format 1", NL;
28
full checksum = "adler32: ", ["-"], WHOLE NUMBER, NL;
29
row count = "num_entries: ", digit, NL;
30
parent_details = WHOLE NUMBER, NULL, NL; XXX: complete this line
31
ghost_details = WHOLE NUMBER, NULL, {GHOST_ID NULL}*, NL;
32
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
33
WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
35
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
36
basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
39
PARENT ROW's are emitted for every parent that is not in the ghosts details
40
line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then
41
each row will have a PARENT ROW for foo and baz, but not for bar.
46
1) Fast end to end use for bzr's top 5 uses cases.
47
2) fall back current object model as needed.
48
3) scale usably to the largest trees known today - say 50K entries.
52
Eventually reuse dirstate objects across locks IFF the dirstate file has not
53
been modified, but will require that we flush/ignore cached stat-hit data
54
because we wont want to restat all files on disk just because a lock was
55
acquired, yet we cannot trust the data after the previous lock was released.
57
Memory representation:
58
vecter of all directories, and vector of the childen ?
60
root_row = (direntry for root, [parent_direntries_for_root]),
62
('', ['data for achild', 'data for bchild', 'data for cchild'])
63
('dir', ['achild', 'cchild', 'echild'])
65
- single bisect to find N subtrees from a path spec
66
- in-order for serialisation - this is 'dirblock' grouping.
67
- insertion of a file '/a' affects only the '/' child-vector, that is, to
68
insert 10K elements from scratch does not generates O(N^2) memoves of a
69
single vector, rather each individual, which tends to be limited to a
70
manageable number. Will scale badly on trees with 10K entries in a
71
single directory. compare with Inventory.InventoryDirectory which has
72
a dictionary for the children. No bisect capability, can only probe for
73
exact matches, or grab all elements and sorta.
74
- Whats the risk of error here? Once we have the base format being processed
75
we should have a net win regardless of optimality. So we are going to
76
go with what seems reasonably.
79
maybe we should do a test profile of these core structure - 10K simulated searches/lookups/etc?
82
The lifetime of Dirstate objects is current per lock, but see above for
83
possible extensions. The lifetime of a row from a dirstate is expected to be
84
very short in the optimistic case: which we are optimising for. For instance,
85
subtree status will determine from analysis of the disk data what rows need to
86
be examined at all, and will be able to determine from a single row whether
87
that file has altered or not, so we are aiming to process tens of thousands of
88
entries each second within the dirstate context, before exposing anything to
89
the larger codebase. This suggests we want the time for a single file
90
comparison to be < 0.1 milliseconds. That would give us 10000 paths per second
91
processed, and to scale to 100 thousand we'll another order of magnitude to do
92
that. Now, as the lifetime for all unchanged entries is the time to parse, stat
93
the file on disk, and then immediately discard, the overhead of object creation
94
becomes a significant cost.
96
Figures: Creating a tuple from from 3 elements was profiled at 0.0625
97
microseconds, whereas creating a object which is subclassed from tuple was
98
0.500 microseconds, and creating an object with 3 elements and slots was 3
99
microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get
100
down to 10 microseconds for the total processing - having 33% of that be object
101
creation is a huge overhead. There is a potential cost in using tuples within
102
each row which is that the conditional code to do comparisons may be slower
103
than method invocation, but method invocation is known to be slow due to stack
104
frame creation, so avoiding methods in these tight inner loops in unfortunately
105
desirable. We can consider a pyrex version of this with objects in future if
123
import bzrlib.inventory
124
from bzrlib import osutils
125
from bzrlib.osutils import (
133
class DirState(object):
134
"""Record directory and metadata state for fast access.
136
A dirstate is a specialised data structure for managing local working
137
tree state information. Its not yet well defined whether it is platform
138
specific, and if it is how we detect/parameterise that.
141
_kind_to_minikind = {'file':'f', 'directory':'d', 'symlink':'l'}
142
_minikind_to_kind = {'f':'file', 'd':'directory', 'l':'symlink'}
143
_to_yesno = {True:'y', False: 'n'} # TODO profile the performance gain
144
# of using int conversion rather than a dict here. AND BLAME ANDREW IF
148
IN_MEMORY_UNMODIFIED = 1
149
IN_MEMORY_MODIFIED = 2
152
NULL_PARENT_ROW = ('', 'file', '/', 'RECYCLED.BIN', 0, False, '')
155
"""Create a DirState object.
159
:attr _root_row: The root row of the directory/file information,
160
- contains the path to / - '', ''
161
- kind of 'directory',
162
- the file id of the root in utf8
165
- and no sha information.
167
# _header_state and _dirblock_state represent the current state
168
# of the dirstate metadata and the per-row data respectiely.
169
# NOT_IN_MEMORY indicates that no data is in memory
170
# IN_MEMORY_UNMODIFIED indicates that what we have in memory
171
# is the same as is on disk
172
# IN_MEMORY_MODIFIED indicates that we have a modified version
173
# of what is on disk.
174
# In future we will add more granularity, for instance _dirblock_state
175
# will probably support partially-in-memory as a separate variable,
176
# allowing for partially-in-memory unmodified and partially-in-memory
178
self._header_state = DirState.NOT_IN_MEMORY
179
self._dirblock_state = DirState.NOT_IN_MEMORY
183
self._root_row = None
184
self._state_file=None
186
def add(self, path, file_id, kind, stat, link_or_sha1):
187
"""Add a path to be tracked.
189
:param path: The path within the dirstate - '' is the root, 'foo' is the
190
path foo within the root, 'foo/bar' is the path bar within foo
192
:param file_id: The file id of the path being added.
193
:param kind: The kind of the path.
194
:param stat: The output of os.lstate for the path.
195
:param link_or_sha1: The sha value of the file, or the target of a
196
symlink. '' for directories.
199
# find the block its in.
200
# find the location in the block.
201
# check its not there
203
#------- copied from bzrlib.inventory.make_entry
204
# --- normalized_filename wants a unicode basename only, so get one.
205
dirname, basename = os.path.split(path)
206
# we dont import normalized_filename directly because we want to be
207
# able to change the implementation at runtime for tests.
208
norm_name, can_access = osutils.normalized_filename(basename)
209
if norm_name != basename:
213
raise errors.InvalidNormalization(path)
214
# now that we've normalised, we need the correct utf8 path and
215
# dirname and basename elements. This single encode and split should be
216
# faster than three separate encodes.
217
utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
218
dirname, basename = os.path.split(utf8path)
219
self._read_dirblocks_if_needed()
220
block_index = self._find_dirblock_index(dirname)
222
# some parent path has not been added - its an error to add this
224
raise errors.NotVersionedError(path, str(self))
225
block = self._dirblocks[block_index][1]
228
packed_stat = DirState.NULLSTAT
231
packed_stat = pack_stat(stat)
232
parent_info = [DirState.NULL_PARENT_ROW] * (len(self._parents) -
235
row_data = ((dirname, basename, kind, file_id.encode('utf8'),
236
size, packed_stat, link_or_sha1), parent_info)
237
elif kind == 'directory':
238
row_data = ((dirname, basename, kind, file_id.encode('utf8'),
239
0, packed_stat, ''), parent_info)
240
elif kind == 'symlink':
241
row_data = ((dirname, basename, kind, file_id.encode('utf8'),
242
size, packed_stat, link_or_sha1), parent_info)
244
raise errors.BzrError('unknown kind %r' % kind)
245
row_index = bisect.bisect_left(block, row_data)
246
if len(block) > row_index:
247
assert block[row_index][0][1] != basename, \
248
"basename %r already added" % basename
249
block.insert(row_index, row_data)
251
if kind == 'directory':
252
# insert a new dirblock
253
self._ensure_block(block_index, row_index, utf8path)
254
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
256
def add_deleted(self, fileid_utf8, parents):
257
"""Add fileid_utf8 with parents as deleted."""
258
self._read_dirblocks_if_needed()
259
new_row = self._make_deleted_row(fileid_utf8, parents)
260
block_index = self._find_dirblock_index(new_row[0][0])
262
# no deleted block yet.
263
bisect.insort_left(self._dirblocks, (new_row[0][0], []))
264
block_index = self._find_dirblock_index(new_row[0][0])
265
block = self._dirblocks[block_index][1]
266
row_index = bisect.insort_left(block, new_row)
267
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
269
def _ensure_block(self, parent_block_index, parent_row_index, dirname):
270
"""Enssure a block for dirname exists.
272
This function exists to let callers which know that there is a
273
directory dirname ensure that the block for it exists. This block can
274
fail to exist because of demand loading, or because a directory had no
275
children. In either case it is not an error. It is however an error to
276
call this if there is no parent entry for the directory, and thus the
277
function requires the coordinates of such an entry to be provided.
279
The root row is special cased and can be indicated with a parent block
282
:param parent_block_index: The index of the block in which dirname's row
284
:param parent_row_index: The index in the parent block where the row
286
:param dirname: The utf8 dirname to ensure there is a block for.
287
:return: The index for the block.
289
# the basename of the directory must be the end of its full name.
290
if not (parent_block_index == -1 and
291
parent_block_index == -1 and dirname == ''):
292
assert dirname.endswith(
293
self._dirblocks[parent_block_index][1][parent_row_index][0][1])
294
## In future, when doing partial parsing, this should load and
295
# populate the entire block.
296
index = bisect.bisect_left(self._dirblocks, (dirname, []))
297
if (index == len(self._dirblocks) or
298
self._dirblocks[index][0] != dirname):
299
self._dirblocks.insert(index, (dirname, []))
302
def _find_dirblock_index(self, dirname):
303
"""Find the dirblock index for dirname.
305
:return: -1 if the dirname is not present, or the index in
306
self._dirblocks for it otherwise.
308
block_index = bisect.bisect_left(self._dirblocks, (dirname, []))
309
if (block_index == len(self._dirblocks) or
310
self._dirblocks[block_index][0] != dirname):
315
def from_tree(tree, dir_state_filename):
316
"""Create a dirstate from a bzr Tree.
318
:param tree: The tree which should provide parent information and
321
# XXX: aka the big ugly.
323
result._state_file = open(dir_state_filename, 'wb+')
325
_encode = base64.encodestring
327
parent_ids = tree.get_parent_ids()
328
num_parents = len(parent_ids)
330
raise ValueError('Cannot handle more than 3 parents')
333
for parent_id in parent_ids:
334
parent_trees.append(tree.branch.repository.revision_tree(parent_id))
336
# FIXME: is this utf8 safe?
338
to_minikind = DirState._kind_to_minikind
339
to_yesno = DirState._to_yesno
341
st = os.lstat(tree.basedir)
344
, 'directory', tree.inventory.root.file_id.encode('utf8')
345
, 0 # no point having a size for dirs.
350
for parent_tree in parent_trees:
351
root_parents.append((
352
parent_tree.inventory.root.revision.encode('utf8'),
360
root_row = (root_info, root_parents)
362
for dirinfo, block in tree.walkdirs():
363
# dirinfo is path, id
365
# add the row for this block
367
dirblocks.append((dirinfo[0], block_row))
368
for relpath, name, kind, st, fileid, versionedkind in block:
370
# unversioned file, skip
372
# TODO? factor out this loop body as a helper function ?
374
dirname, basename = os.path.split(relpath.encode('utf8'))
376
s = tree.get_file_sha1(fileid, relpath)
377
elif kind == 'directory':
378
if name in ('.bzr', '.hg', 'CVS', '.svn', '_svn'):
379
raise Exception('skipping dirs not supported yet')
380
# Skip this, and all children
381
to_remove.append((relpath, name, kind, st, abspath))
385
elif kind == 'symlink':
386
# sha value of the link target ?!
387
s = os.readlink(abspath)
389
for count in xrange(num_parents):
391
result._parent_info(parent_trees[count], fileid))
392
row_data = (dirname.encode('utf8'), basename.encode('utf8'),
393
kind, fileid.encode('utf8'), st.st_size, pack_stat(st),
395
block_row.append((row_data, parent_info))
397
# It isn't safe to remove entries while we are iterating
398
# over the same list, so remove them now
399
for entry in to_remove:
402
#lines.append(result._get_parents_line(parent_ids))
403
#lines.append(result._get_ghosts_line([]))
404
result._set_data(parent_ids, root_row, dirblocks)
408
def get_ghosts(self):
409
"""Return a list of the parent tree revision ids that are ghosts."""
410
self._read_header_if_needed()
414
"""Serialise the entire dirstate to a sequence of lines."""
415
if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and
416
self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):
417
# read whats on disk.
418
self._state_file.seek(0)
419
return self._state_file.readlines()
421
lines.append(self._get_parents_line(self.get_parent_ids()))
422
lines.append(self._get_ghosts_line(self._ghosts))
423
# append the root line which is special cased
424
lines.extend(map(self._row_to_line, self._iter_rows()))
425
return self._get_output_lines(lines)
427
def _get_ghosts_line(self, ghost_ids):
428
"""Create a line for the state file for ghost information."""
429
return '\0'.join([str(len(ghost_ids))] +
430
[g.encode('utf8') for g in ghost_ids])
432
def _get_parents_line(self, parent_ids):
433
"""Create a line for the state file for parents information."""
434
return '\0'.join([str(len(parent_ids))] +
435
[p.encode('utf8') for p in parent_ids])
437
def get_parent_ids(self):
438
"""Return a list of the parent tree ids for the directory state."""
439
self._read_header_if_needed()
440
return list(self._parents)
442
def _get_row(self, path_utf8):
443
"""Get the dirstate row for path.
445
:param path_utf8: An utf8 path to be looked up.
446
:return: The dirstate row tuple for path, or (None, None)
448
self._read_dirblocks_if_needed()
450
return self._root_row
451
dirname, basename = os.path.split(path_utf8)
452
block_index, row_index, dir_present, file_present = \
453
self._get_block_row_index(dirname, basename)
456
row = self._dirblocks[block_index][1][row_index]
457
assert row[0][3], 'unversioned row?!?!'
460
def _get_block_row_index(self, dirname, basename):
461
"""Get the coordinates for a path in the state structure.
463
:param dirname: The utf8 dirname to lookup.
464
:param basename: The utf8 basename to lookup.
465
:return: A tuple describing where the path is located, or should be
466
inserted. The tuple contains four fields: the block index, the row
467
index, anda two booleans are True when the directory is present, and
468
when the entire path is present. There is no guarantee that either
469
coordinate is currently reachable unless the found field for it is
470
True. For instance, a directory not present in the state may be
471
returned with a value one greater than the current highest block
472
offset. The directory present field will always be True when the
473
path present field is True.
475
assert not (dirname == '' and basename == ''), 'blackhole lookup error'
476
self._read_dirblocks_if_needed()
477
block_index = bisect.bisect_left(self._dirblocks, (dirname, []))
478
if (block_index == len(self._dirblocks) or
479
self._dirblocks[block_index][0] != dirname):
480
# no such directory - return the dir index and 0 for the row.
481
return block_index, 0, False, False
482
block = self._dirblocks[block_index][1] # access the rows only
483
search = ((dirname, basename), [])
484
row_index = bisect.bisect_left(block, search)
485
if row_index == len(block) or block[row_index][0][1] != basename:
486
return block_index, row_index, True, False
487
return block_index, row_index, True, True
490
def initialize(path):
491
"""Create a new dirstate on path.
493
The new dirstate will be an empty tree - that is it has no parents,
494
and only a root node - which has id ROOT_ID.
496
:param path: The name of the file for the dirstate.
497
:return: A DirState object.
499
# This constructs a new DirState object on a path, sets the _state_file
500
# to a new empty file for that path. It then calls _set_data() with our
501
# stock empty dirstate information - a root with ROOT_ID, no children,
502
# and no parents. Finally it calls save() to ensure that this data will
505
result._state_file = open(path, 'wb+')
506
# a new root directory, with a pack_stat (the x's) that is just noise and will
507
# never match the output of base64 encode.
508
root_row_data = ('', '', 'directory', bzrlib.inventory.ROOT_ID, 0,
509
DirState.NULLSTAT, '')
511
root_row = (root_row_data, root_parents)
512
empty_tree_dirblocks = [('', [])] # root dir contents - no entries.
513
result._set_data([], root_row, empty_tree_dirblocks)
517
result._state_file.close()
521
def _iter_rows(self):
522
"""Iterate over all the row data in the dirstate.
524
Each yelt item is a tuple of (row_data, parent_data_list).
526
self._read_dirblocks_if_needed()
528
for directory in self._dirblocks:
529
for row in directory[1]:
532
def _get_output_lines(self, lines):
533
"""format lines for final output.
535
:param lines: A sequece of lines containing the parents list and the
538
output_lines = ['#bazaar dirstate flat format 1\n']
539
lines.append('') # a final newline
540
inventory_text = '\0\n\0'.join(lines)
541
output_lines.append('adler32: %s\n' % (zlib.adler32(inventory_text),))
542
# -3, 1 for num parents, 1 for ghosts, 1 for final newline
543
num_entries = len(lines)-3
544
output_lines.append('num_entries: %s\n' % (num_entries,))
545
output_lines.append(inventory_text)
548
def _make_deleted_row(self, fileid_utf8, parents):
549
"""Return a deleted for for fileid_utf8."""
550
return ('/', 'RECYCLED.BIN', 'file', fileid_utf8, 0, DirState.NULLSTAT,
555
"""Construct a DirState on the file at path path."""
557
result._state_file = open(path, 'rb+')
560
def _parent_info(self, parent_tree, fileid):
561
"""Generate the parent information for file_id in parent_tree."""
562
# FIXME: This is probably expensive - we encode the path that in the
563
# common case will be the same across all parents, twice.
564
# also, id2path is slow in inventory, and we should make that fast.
566
parent_entry = parent_tree.inventory[fileid]
567
except errors.NoSuchId:
568
# this parent does not have fileid - return a bogus entry, which
569
# will be filtered out on iteration etc.
570
# an empty revision id is bogus and safe to put on disk
571
# we make it be a 'file', just because. We give it the
572
# deleted file path dirname and basename, 0 size, not executable
574
return DirState.NULL_PARENT_ROW
575
parent_path = parent_tree.inventory.id2path(fileid)
576
dirname, basename = os.path.split(parent_path.encode('utf8'))
577
return (parent_entry.revision.encode('utf8'),
579
# FIXME: set these from the parent
581
parent_entry.text_size or 0,
582
parent_entry.executable,
583
parent_entry.text_sha1 or '',
586
def _read_dirblocks_if_needed(self):
587
"""Read in all the dirblocks from the file if they are not in memory."""
588
self._read_header_if_needed()
589
if self._dirblock_state == DirState.NOT_IN_MEMORY:
590
# the _state_file pointer will be positioned at the start of the
592
text = self._state_file.read()
593
# TODO: check the adler checksums. adler_measured = zlib.adler32(text)
595
fields = text.split('\0')
596
# Remove the last blank entry
597
trailing = fields.pop()
598
assert trailing == ''
599
# consider turning fields into a tuple.
601
# skip the first field which is the trailing null from the header.
603
# Each line now has an extra '\n' field which is not used
604
# so we just skip over it
605
# number of fields per dir_entry
606
# + number of fields per parent_entry
608
num_present_parents = len(self._parents) - len(self._ghosts)
609
entry_size = 7 + (7 * (num_present_parents)) + 1
610
expected_field_count = entry_size * self._num_entries
611
if len(fields) - cur > expected_field_count:
612
fields = fields[:expected_field_count + cur]
613
trace.mutter('Unexpectedly long dirstate field count!')
614
print "XXX: incorrectly truncated dirstate file bug triggered."
615
field_count = len(fields)
616
# this checks our adjustment, and also catches file too short.
617
assert field_count - cur == expected_field_count, \
618
'field count incorrect %s != %s, entry_size=%s, '\
619
'num_entries=%s fields=%r' % (
620
field_count - cur, expected_field_count, entry_size,
621
self._num_entries, fields)
623
# Fast path the case where there are 1 or 2 parents
624
if num_present_parents == 0:
625
entries = [(fields[pos:pos+7], []) for pos in xrange(cur, field_count, entry_size)]
626
elif num_present_parents == 1:
627
entries = [(fields[pos:pos+7], [fields[pos+7:pos+14],])
628
for pos in xrange(cur, field_count, entry_size)]
629
elif num_present_parents == 2:
630
entries = [(fields[pos:pos+7], [
631
fields[pos+7:pos+14],
632
fields[pos+14:pos+21],])
633
for pos in xrange(cur, field_count, entry_size)]
637
tuple([fields[chunk:chunk+7] for
638
chunk in xrange(pos + 7, pos+entry_size-1, 7)]))
639
for pos in xrange(cur, field_count, entry_size)
642
assert len(entries) == self._num_entries, '%s != %s entries' % (len(entries),
645
def _line_to_row(line):
646
"""Convert a freshly read line's size and minikind for use."""
647
# convert the minikind to kind
648
line[0][2] = self._minikind_to_kind[line[0][2]]
649
# convert the size to an int
650
line[0][4] = int(line[0][4])
651
for parent in line[1]:
652
parent[1] = self._minikind_to_kind[parent[1]]
653
parent[4] = int(parent[4])
654
parent[5] = parent[5] == 'y'
655
return tuple(line[0]), map(tuple, line[1])
656
new_rows = map(_line_to_row, entries)
657
self._rows_to_current_state(new_rows)
658
self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
660
def _read_header(self):
661
"""This reads in the metadata header, and the parent ids.
663
After reading in, the file should be positioned at the null
664
just before the start of the first record in the file.
666
:return: (expected adler checksum, number of entries, parent list)
669
parent_line = self._state_file.readline()
670
info = parent_line.split('\0')
671
num_parents = int(info[0])
672
assert num_parents == len(info)-2, 'incorrect parent info line'
673
self._parents = [p.decode('utf8') for p in info[1:-1]]
675
ghost_line = self._state_file.readline()
676
info = ghost_line.split('\0')
677
num_ghosts = int(info[1])
678
assert num_ghosts == len(info)-3, 'incorrect ghost info line'
679
self._ghosts = [p.decode('utf8') for p in info[2:-1]]
680
self._header_state = DirState.IN_MEMORY_UNMODIFIED
682
def _read_header_if_needed(self):
683
"""Read the header of the dirstate file if needed."""
684
if self._header_state == DirState.NOT_IN_MEMORY:
687
def _read_prelude(self):
688
"""Read in the prelude header of the dirstate file
690
This only reads in the stuff that is not connected to the adler
691
checksum. The position will be correct to read in the rest of
692
the file and check the checksum after this point.
693
The next entry in the file should be the number of parents,
694
and their ids. Followed by a newline.
696
header = self._state_file.readline()
697
assert header == '#bazaar dirstate flat format 1\n', \
698
'invalid header line: %r' % (header,)
699
adler_line = self._state_file.readline()
700
assert adler_line.startswith('adler32: '), 'missing adler32 checksum'
701
self.adler_expected = int(adler_line[len('adler32: '):-1])
702
num_entries_line = self._state_file.readline()
703
assert num_entries_line.startswith('num_entries: '), 'missing num_entries line'
704
self._num_entries = int(num_entries_line[len('num_entries: '):-1])
706
def _row_to_line(self, row):
707
"""Serialize row to a NULL delimited line ready for _get_output_lines.
709
:param row: A row_tuple as defined in the module docstring.
711
entire_row = list(row[0])
712
for parent_number, parent_data in enumerate(row[1]):
713
# (revision, kind, dirname, basename, size, executable_bool, sha1)
714
entire_row.extend(parent_data)
715
# minikind conversion of the parent
716
parent_offset = 7 + parent_number * 7
717
entire_row[parent_offset + 1] = DirState._kind_to_minikind[parent_data[1]]
718
entire_row[parent_offset + 4] = str(parent_data[4])
719
entire_row[parent_offset + 5] = DirState._to_yesno[parent_data[5]]
720
# conversion from memory to disk-ready format:
721
# minikind conversion of the current row type.
722
entire_row[2] = DirState._kind_to_minikind[entire_row[2]]
723
entire_row[4] = str(entire_row[4])
724
# minikind of parents
725
return '\0'.join(entire_row)
727
def _rows_to_current_state(self, new_rows):
728
"""Load new_rows into self._root_row and self.dirblocks.
730
Process new_rows into the current state object, making them the active
733
:param new_rows: A sorted list of rows. This function does not sort
734
to prevent unneeded overhead when callers have a sorted list
738
assert new_rows[0][0][0:2] == ('', ''), \
739
"Incorrect root row %r" % new_rows[0][0]
740
self._root_row = new_rows[0]
741
self._dirblocks = [('', [])]
742
for row in new_rows[1:]:
743
if row[0][0] != self._dirblocks[-1][0]:
745
self._dirblocks.append((row[0][0], []))
746
# append the row to the current block
747
self._dirblocks[-1][1].append(row)
750
"""Save any pending changes created during this session.
752
We reuse the existing file, because that prevents race conditions with
753
file creation, and we expect to be using oslocks on it in the near
754
future to prevent concurrent modification and reads - because dirstates
755
incremental data aggretation is not compatible with reading a modified
756
file, and replacing a file in use by another process is impossible on
759
A dirstate in read only mode should be smart enough though to validate
760
that the file has not changed, and otherwise discard its cache and
761
start over, to allow for fine grained read lock duration, so 'status'
762
wont block 'commit' - for example.
764
if (self._header_state == DirState.IN_MEMORY_MODIFIED or
765
self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
766
self._state_file.seek(0)
767
self._state_file.writelines(self.get_lines())
768
self._state_file.truncate()
769
self._state_file.flush()
770
self._header_state = DirState.IN_MEMORY_UNMODIFIED
771
self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED
773
def _set_data(self, parent_ids, root_row, dirblocks):
774
"""Set the full dirstate data in memory.
776
This is an internal function used to completely replace the objects
777
in memory state. It puts the dirstate into state 'full-dirty'.
779
:param parent_ids: A list of parent tree revision ids.
780
:param root_row: The root row - a tuple of the root direntry and the
781
list of matching direntries from the parent_ids trees.
782
:param dirblocks: A list containing one tuple for each directory in the
783
tree. Each tuple contains the directory path and a list of
784
row data in the same format as root_row.
786
# our memory copy is now authoritative.
787
self._dirblocks = dirblocks
788
self._root_row = root_row
789
self._header_state = DirState.IN_MEMORY_MODIFIED
790
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
791
self._parents = list(parent_ids)
793
def set_path_id(self, path, new_id):
794
"""Change the id of path to new_id.
796
:param path: The path inside the tree to set - '' is the root, 'foo'
797
is the path foo in the root.
798
:param new_id: The new id to assign to the path. If unicode, it will
799
be encoded to utf8. In future this will be deprecated: avoid using
800
unicode ids if possible.
802
# TODO: start warning here.
803
if new_id.__class__ == unicode:
804
new_id = new_id.encode('utf8')
805
self._read_dirblocks_if_needed()
806
if new_id == self._root_row[0][3]:
807
# the root id is unchanged
809
if len(path) or len(self._parents):
810
import pdb;pdb.set_trace()
812
raise NotImplementedError(self.set_path_id)
813
root_info, root_parents = self._root_row
814
self._root_row = (root_info[0:3] + (new_id, ) + root_info[4:7]), root_parents
815
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
817
def set_parent_trees(self, trees, ghosts):
818
"""Set the parent trees for the dirstate.
820
:param trees: A list of revision_id, tree tuples. tree must be provided
821
even if the revision_id refers to a ghost: supply an empty tree in
823
:param ghosts: A list of the revision_ids that are ghosts at the time
826
# TODO: generate a list of parent indexes to preserve to save
827
# processing specific parent trees. In the common case one tree will
828
# be preserved - the left most parent.
829
# TODO: if the parent tree is a dirstate, we might want to walk them
830
# all by path in parallel for 'optimal' common-case performance.
831
# generate new root row.
832
self._read_dirblocks_if_needed()
833
old_root = self._root_row
834
root_info = self._root_row[0]
835
new_parent_count = len(trees)
836
# sketch: loop over all rows in the dirstate, cherry picking
837
# entries from the parent trees, if they are not ghosts.
838
# after we finish walking the dirstate, all entries not in the dirstate
839
# are deletes, so we want to append them to the end as per the design
840
# discussions. So do a set difference on ids with the parents to
841
# get deletes, and add them to the end.
843
# skip ghost trees, as they dont get represented.
844
parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
845
parent_tree_count = len(parent_trees)
846
# loop over existing entries in the dirstate.
848
for entry, old_parents in self._iter_rows():
850
checked_ids.add(file_id)
851
new_parents = [None] * parent_tree_count
852
for position, parent_tree in enumerate(parent_trees):
853
# revision_utf8, KIND, dirname, basename, size, executable, sha
854
new_parents[position] = self._parent_info(parent_tree, file_id)
855
assert None not in new_parents
856
new_rows.append((entry, new_parents))
857
# get additional ids that are present in parents and not in this tree.
859
for tree in parent_trees:
860
deleted_ids.update(set(tree.inventory._byid).difference(checked_ids))
861
# add the deleted ids to the dirstate. deleted files are represented as
862
# a file with dirname '', basename ''
863
for file_id in deleted_ids:
864
# add these ids to the deleted block
865
checked_ids.add(file_id)
866
# deleted items have a synthetic entry.
867
entry = ('/', 'RECYCLED.BIN', 'file', file_id.encode('utf8'), 0,
868
DirState.NULLSTAT, '')
869
new_parents = [None] * parent_tree_count
870
for position, parent_tree in enumerate(parent_trees):
871
# revision_utf8, KIND, dirname, basename, size, executable, sha
872
new_parents[position] = self._parent_info(parent_tree, file_id)
873
assert None not in new_parents
874
new_rows.append((entry, new_parents))
877
new_rows = sorted(new_rows)
878
self._rows_to_current_state(new_rows)
879
self._parents = [rev_id for rev_id, tree in trees]
880
self._ghosts = list(ghosts)
881
self._header_state = DirState.IN_MEMORY_MODIFIED
882
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
884
def set_state_from_inventory(self, new_inv):
885
"""Set new_inv as the current state.
887
:param new_inv: The inventory object to set current state from.
889
self._read_dirblocks_if_needed()
891
# generate a byid index of the dirstate
893
for row, parents in self._iter_rows():
894
parent_rows[row[3]] = parents
896
num_present_parents = len(self._parents) - len(self._ghosts)
897
# walk the new inventory in directory order, copying parent data
900
for path, entry in new_inv.iter_entries_by_dir():
901
dirname, basename = os.path.split(path.encode('utf8'))
903
fileid_utf8 = entry.file_id.encode('utf8')
905
size = entry.text_size or 0
906
sha1 = entry.text_sha1 or ''
907
elif kind == 'symlink':
909
sha1 = (entry.symlink_target or '').encode('utf8')
914
parents = parent_rows[fileid_utf8]
915
del parent_rows[fileid_utf8]
917
parents = [DirState.NULL_PARENT_ROW] * num_present_parents
918
new_row = (dirname, basename, kind, fileid_utf8, size, DirState.NULLSTAT, sha1), parents
919
new_rows.append(new_row)
920
# append deleted data to the end of the tree as usual.
921
for fileid_utf8, parents in parent_rows.items():
923
# this row was only present in the old state, had no parents
925
# deleted items have a synthetic entry.
926
new_row = ('/', 'RECYCLED.BIN', 'file', fileid_utf8, 0,
927
DirState.NULLSTAT, ''), parents
928
new_rows.append(new_row)
930
# sort all the rows (the ones in parents not in current may be unsorted)
931
new_rows = sorted(new_rows)
932
self._rows_to_current_state(new_rows)
933
self._dirblock_state = DirState.IN_MEMORY_MODIFIED
936
def pack_stat(st, _encode=base64.encodestring, _pack=struct.pack):
937
"""Convert stat values into a packed representation."""
938
# jam 20060614 it isn't really worth removing more entries if we
939
# are going to leave it in packed form.
940
# With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
941
# With all entries filesize is 5.9M and read time is mabye 280ms
942
# well within the noise margin
944
# base64.encode always adds a final newline, so strip it off
945
return _encode(_pack('>llllll'
946
, st.st_size, st.st_mtime, st.st_ctime
947
, st.st_dev, st.st_ino, st.st_mode))[:-1]
added
removed
bzrlib/dirstate.py
