1
# Copyright (C) 2005 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
"""Tree classes, representing directory at point in time.
21
from cStringIO import StringIO
22
from warnings import warn
25
from bzrlib import delta, osutils
26
from bzrlib.decorators import needs_read_lock
27
from bzrlib.errors import BzrError, BzrCheckError
28
from bzrlib import errors
29
from bzrlib.inventory import Inventory
30
from bzrlib.inter import InterObject
31
from bzrlib.osutils import fingerprint_file
32
import bzrlib.revision
33
from bzrlib.trace import mutter, note
37
"""Abstract file tree.
39
There are several subclasses:
41
* `WorkingTree` exists as files on disk editable by the user.
43
* `RevisionTree` is a tree as recorded at some point in the past.
45
Trees contain an `Inventory` object, and also know how to retrieve
46
file texts mentioned in the inventory, either from a working
47
directory or from a store.
49
It is possible for trees to contain files that are not described
50
in their inventory or vice versa; for this use `filenames()`.
52
Trees can be compared, etc, regardless of whether they are working
53
trees or versioned trees.
56
def changes_from(self, other, want_unchanged=False, specific_files=None,
57
extra_trees=None, require_versioned=False):
58
"""Return a TreeDelta of the changes from other to this tree.
60
:param other: A tree to compare with.
61
:param specific_files: An optional list of file paths to restrict the
62
comparison to. When mapping filenames to ids, all matches in all
63
trees (including optional extra_trees) are used, and all children of
64
matched directories are included.
65
:param want_unchanged: An optional boolean requesting the inclusion of
66
unchanged entries in the result.
67
:param extra_trees: An optional list of additional trees to use when
68
mapping the contents of specific_files (paths) to file_ids.
69
:param require_versioned: An optional boolean (defaults to False). When
70
supplied and True all the 'specific_files' must be versioned, or
71
a PathsNotVersionedError will be thrown.
73
The comparison will be performed by an InterTree object looked up on
76
# Martin observes that Tree.changes_from returns a TreeDelta and this
77
# may confuse people, because the class name of the returned object is
78
# a synonym of the object referenced in the method name.
79
return InterTree.get(other, self).compare(
80
want_unchanged=want_unchanged,
81
specific_files=specific_files,
82
extra_trees=extra_trees,
83
require_versioned=require_versioned,
86
def iter_changes(self, from_tree, include_unchanged=False,
87
specific_file_ids=None):
88
intertree = InterTree.get(from_tree, self)
89
return intertree.iter_changes(from_tree, self, include_unchanged,
93
"""Get a list of the conflicts in the tree.
95
Each conflict is an instance of bzrlib.conflicts.Conflict.
99
def get_parent_ids(self):
100
"""Get the parent ids for this tree.
102
:return: a list of parent ids. [] is returned to indicate
103
a tree with no parents.
104
:raises: BzrError if the parents are not known.
106
raise NotImplementedError(self.get_parent_ids)
108
def has_filename(self, filename):
109
"""True if the tree has given filename."""
110
raise NotImplementedError()
112
def has_id(self, file_id):
113
return self.inventory.has_id(file_id)
115
__contains__ = has_id
117
def has_or_had_id(self, file_id):
118
if file_id == self.inventory.root.file_id:
120
return self.inventory.has_id(file_id)
123
return iter(self.inventory)
125
def id2path(self, file_id):
126
return self.inventory.id2path(file_id)
128
def iter_entries_by_dir(self):
129
"""Walk the tree in 'by_dir' order.
131
This will yield each entry in the tree as a (path, entry) tuple. The
132
order that they are yielded is: the contents of a directory are
133
preceeded by the parent of a directory, and all the contents of a
134
directory are grouped together.
136
return self.inventory.iter_entries_by_dir()
138
def kind(self, file_id):
139
raise NotImplementedError("subclasses must implement kind")
141
def _get_inventory(self):
142
return self._inventory
144
def get_file_by_path(self, path):
145
return self.get_file(self._inventory.path2id(path))
147
inventory = property(_get_inventory,
148
doc="Inventory of this Tree")
150
def _check_retrieved(self, ie, f):
153
fp = fingerprint_file(f)
156
if ie.text_size is not None:
157
if ie.text_size != fp['size']:
158
raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
159
["inventory expects %d bytes" % ie.text_size,
160
"file is actually %d bytes" % fp['size'],
161
"store is probably damaged/corrupt"])
163
if ie.text_sha1 != fp['sha1']:
164
raise BzrError("wrong SHA-1 for file %r in %r" % (ie.file_id, self._store),
165
["inventory expects %s" % ie.text_sha1,
166
"file is actually %s" % fp['sha1'],
167
"store is probably damaged/corrupt"])
170
def print_file(self, file_id):
171
"""Print file with id `file_id` to stdout."""
173
sys.stdout.write(self.get_file_text(file_id))
179
"""What files are present in this tree and unknown.
181
:return: an iterator over the unknown files.
188
def filter_unversioned_files(self, paths):
189
"""Filter out paths that are not versioned.
191
:return: set of paths.
193
# NB: we specifically *don't* call self.has_filename, because for
194
# WorkingTrees that can indicate files that exist on disk but that
196
pred = self.inventory.has_filename
197
return set((p for p in paths if not pred(p)))
201
from bzrlib.revisiontree import RevisionTree
204
class EmptyTree(Tree):
207
self._inventory = Inventory()
208
warn('EmptyTree is deprecated as of bzr 0.9 please use '
209
'repository.revision_tree instead.',
210
DeprecationWarning, stacklevel=2)
212
def get_parent_ids(self):
215
def get_symlink_target(self, file_id):
218
def has_filename(self, filename):
221
def kind(self, file_id):
222
assert self._inventory[file_id].kind == "directory"
225
def list_files(self):
228
def __contains__(self, file_id):
229
return (file_id in self._inventory)
231
def get_file_sha1(self, file_id, path=None):
235
######################################################################
238
# TODO: Merge these two functions into a single one that can operate
239
# on either a whole tree or a set of files.
241
# TODO: Return the diff in order by filename, not by category or in
242
# random order. Can probably be done by lock-stepping through the
243
# filenames from both trees.
246
def file_status(filename, old_tree, new_tree):
247
"""Return single-letter status, old and new names for a file.
249
The complexity here is in deciding how to represent renames;
250
many complex cases are possible.
252
old_inv = old_tree.inventory
253
new_inv = new_tree.inventory
254
new_id = new_inv.path2id(filename)
255
old_id = old_inv.path2id(filename)
257
if not new_id and not old_id:
258
# easy: doesn't exist in either; not versioned at all
259
if new_tree.is_ignored(filename):
260
return 'I', None, None
262
return '?', None, None
264
# There is now a file of this name, great.
267
# There is no longer a file of this name, but we can describe
268
# what happened to the file that used to have
269
# this name. There are two possibilities: either it was
270
# deleted entirely, or renamed.
272
if new_inv.has_id(old_id):
273
return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
275
return 'D', old_inv.id2path(old_id), None
277
# if the file_id is new in this revision, it is added
278
if new_id and not old_inv.has_id(new_id):
281
# if there used to be a file of this name, but that ID has now
282
# disappeared, it is deleted
283
if old_id and not new_inv.has_id(old_id):
290
def find_renames(old_inv, new_inv):
291
for file_id in old_inv:
292
if file_id not in new_inv:
294
old_name = old_inv.id2path(file_id)
295
new_name = new_inv.id2path(file_id)
296
if old_name != new_name:
297
yield (old_name, new_name)
300
def find_ids_across_trees(filenames, trees, require_versioned=True):
301
"""Find the ids corresponding to specified filenames.
303
All matches in all trees will be used, and all children of matched
304
directories will be used.
306
:param filenames: The filenames to find file_ids for
307
:param trees: The trees to find file_ids within
308
:param require_versioned: if true, all specified filenames must occur in
310
:return: a set of file ids for the specified filenames and their children.
314
specified_ids = _find_filename_ids_across_trees(filenames, trees,
316
return _find_children_across_trees(specified_ids, trees)
319
def _find_filename_ids_across_trees(filenames, trees, require_versioned):
320
"""Find the ids corresponding to specified filenames.
322
All matches in all trees will be used.
324
:param filenames: The filenames to find file_ids for
325
:param trees: The trees to find file_ids within
326
:param require_versioned: if true, all specified filenames must occur in
328
:return: a set of file ids for the specified filenames
331
interesting_ids = set()
332
for tree_path in filenames:
335
file_id = tree.inventory.path2id(tree_path)
336
if file_id is not None:
337
interesting_ids.add(file_id)
340
not_versioned.append(tree_path)
341
if len(not_versioned) > 0 and require_versioned:
342
raise errors.PathsNotVersionedError(not_versioned)
343
return interesting_ids
346
def _find_children_across_trees(specified_ids, trees):
347
"""Return a set including specified ids and their children
349
All matches in all trees will be used.
351
:param trees: The trees to find file_ids within
352
:return: a set containing all specified ids and their children
354
interesting_ids = set(specified_ids)
355
pending = interesting_ids
356
# now handle children of interesting ids
357
# we loop so that we handle all children of each id in both trees
358
while len(pending) > 0:
360
for file_id in pending:
362
if file_id not in tree:
364
entry = tree.inventory[file_id]
365
for child in getattr(entry, 'children', {}).itervalues():
366
if child.file_id not in interesting_ids:
367
new_pending.add(child.file_id)
368
interesting_ids.update(new_pending)
369
pending = new_pending
370
return interesting_ids
373
class InterTree(InterObject):
374
"""This class represents operations taking place between two Trees.
376
Its instances have methods like 'compare' and contain references to the
377
source and target trees these operations are to be carried out on.
379
clients of bzrlib should not need to use InterTree directly, rather they
380
should use the convenience methods on Tree such as 'Tree.compare()' which
381
will pass through to InterTree as appropriate.
387
def compare(self, want_unchanged=False, specific_files=None,
388
extra_trees=None, require_versioned=False):
389
"""Return the changes from source to target.
391
:return: A TreeDelta.
392
:param specific_files: An optional list of file paths to restrict the
393
comparison to. When mapping filenames to ids, all matches in all
394
trees (including optional extra_trees) are used, and all children of
395
matched directories are included.
396
:param want_unchanged: An optional boolean requesting the inclusion of
397
unchanged entries in the result.
398
:param extra_trees: An optional list of additional trees to use when
399
mapping the contents of specific_files (paths) to file_ids.
400
:param require_versioned: An optional boolean (defaults to False). When
401
supplied and True all the 'specific_files' must be versioned, or
402
a PathsNotVersionedError will be thrown.
404
# NB: show_status depends on being able to pass in non-versioned files and
405
# report them as unknown
406
trees = (self.source, self.target)
407
if extra_trees is not None:
408
trees = trees + tuple(extra_trees)
409
specific_file_ids = find_ids_across_trees(specific_files,
410
trees, require_versioned=require_versioned)
411
if specific_files and not specific_file_ids:
412
# All files are unversioned, so just return an empty delta
413
# _compare_trees would think we want a complete delta
414
return delta.TreeDelta()
415
return delta._compare_trees(self.source, self.target, want_unchanged,
418
def iter_changes(self, from_tree, to_tree, include_unchanged,
420
"""Generate an iterator of changes between trees.
423
(file_id, path, changed_content, versioned, parent, name, kind,
426
Path is relative to the to_tree. changed_content is True if the file's
427
content has changed. This includes changes to its kind, and to
430
versioned, parent, name, kind, executable are tuples of (from, to) if
431
changed. If a file is missing in a tree, its kind is None.
433
Iteration is done in parent-to-child order, relative to the to_tree.
435
def get_versioned_kind(tree, file_id):
437
return tree.kind(file_id)
438
except errors.NoSuchFile:
442
if specific_file_ids is not None:
443
specific_file_ids = set(specific_file_ids)
444
for path, to_entry in to_tree.iter_entries_by_dir():
445
file_id = to_entry.file_id
446
to_paths[file_id] = path
447
if (specific_file_ids is not None and
448
file_id not in specific_file_ids):
450
changed_content = False
451
from_versioned = (file_id in from_tree)
452
versioned = (from_versioned, True)
454
from_kind = get_versioned_kind(from_tree, file_id)
455
if from_kind is not None:
456
from_executable = (from_tree.is_executable(file_id) not in
459
from_executable = None
460
from_entry = from_tree.inventory[file_id]
461
from_parent = from_entry.parent_id
462
from_name = from_entry.name
467
from_executable = None
468
to_kind = get_versioned_kind(to_tree, file_id)
469
kind = (from_kind, to_kind)
470
if kind[0] != kind[1]:
471
changed_content = True
472
elif from_kind == 'file':
473
if (from_tree.get_file_sha1(file_id) !=
474
to_tree.get_file_sha1(file_id)):
475
changed_content = True
476
elif from_kind == 'symlink':
477
if (from_tree.get_symlink_target(file_id) !=
478
to_tree.get_symlink_target(file_id)):
479
changed_content = True
480
parent = (from_parent, to_entry.parent_id)
481
name = (from_name, to_entry.name)
482
if to_kind is not None:
483
to_executable = (to_tree.is_executable(file_id) not in
487
executable = (from_executable, to_executable)
488
if (changed_content is not False or versioned[0] != versioned[1]
489
or parent[0] != parent[1] or name[0] != name[1] or
490
executable[0] != executable[1] or include_unchanged):
491
yield (file_id, path, changed_content, versioned, parent,
492
name, kind, executable)
494
for path, from_entry in from_tree.iter_entries_by_dir():
495
file_id = from_entry.file_id
496
if file_id in to_paths:
498
to_path = osutils.pathjoin(to_paths[from_entry.parent_id],
500
to_paths[file_id] = to_path
501
if (specific_file_ids is not None and
502
file_id not in specific_file_ids):
504
versioned = (True, False)
505
parent = (from_entry.parent_id, None)
506
name = (from_entry.name, None)
507
kind = (get_versioned_kind(from_tree, file_id), None)
508
if kind[0] is not None:
509
from_executable = (from_tree.is_executable(file_id) not in
512
from_executable = False
513
executable = (from_executable, None)
514
changed_content = True
515
# the parent's path is necessarily known at this point.
516
yield(file_id, to_path, changed_content, versioned, parent,
517
name, kind, executable)
added
removed
bzrlib/tree.py
