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
29
from bzrlib.decorators import needs_read_lock
30
from bzrlib.errors import BzrError, BzrCheckError
31
from bzrlib import errors
32
from bzrlib.inventory import Inventory
33
from bzrlib.inter import InterObject
34
from bzrlib.osutils import fingerprint_file
35
import bzrlib.revision
36
from bzrlib.trace import mutter, note
40
"""Abstract file tree.
42
There are several subclasses:
44
* `WorkingTree` exists as files on disk editable by the user.
46
* `RevisionTree` is a tree as recorded at some point in the past.
48
Trees contain an `Inventory` object, and also know how to retrieve
49
file texts mentioned in the inventory, either from a working
50
directory or from a store.
52
It is possible for trees to contain files that are not described
53
in their inventory or vice versa; for this use `filenames()`.
55
Trees can be compared, etc, regardless of whether they are working
56
trees or versioned trees.
59
def changes_from(self, other, want_unchanged=False, specific_files=None,
60
extra_trees=None, require_versioned=False, include_root=False):
61
"""Return a TreeDelta of the changes from other to this tree.
63
:param other: A tree to compare with.
64
:param specific_files: An optional list of file paths to restrict the
65
comparison to. When mapping filenames to ids, all matches in all
66
trees (including optional extra_trees) are used, and all children of
67
matched directories are included.
68
:param want_unchanged: An optional boolean requesting the inclusion of
69
unchanged entries in the result.
70
:param extra_trees: An optional list of additional trees to use when
71
mapping the contents of specific_files (paths) to file_ids.
72
:param require_versioned: An optional boolean (defaults to False). When
73
supplied and True all the 'specific_files' must be versioned, or
74
a PathsNotVersionedError will be thrown.
76
The comparison will be performed by an InterTree object looked up on
79
# Martin observes that Tree.changes_from returns a TreeDelta and this
80
# may confuse people, because the class name of the returned object is
81
# a synonym of the object referenced in the method name.
82
return InterTree.get(other, self).compare(
83
want_unchanged=want_unchanged,
84
specific_files=specific_files,
85
extra_trees=extra_trees,
86
require_versioned=require_versioned,
87
include_root=include_root
90
def _iter_changes(self, from_tree, include_unchanged=False,
91
specific_files=None, pb=None, extra_trees=None,
92
require_versioned=True):
93
intertree = InterTree.get(from_tree, self)
94
return intertree._iter_changes(include_unchanged, specific_files, pb,
95
extra_trees, require_versioned)
98
"""Get a list of the conflicts in the tree.
100
Each conflict is an instance of bzrlib.conflicts.Conflict.
104
def get_parent_ids(self):
105
"""Get the parent ids for this tree.
107
:return: a list of parent ids. [] is returned to indicate
108
a tree with no parents.
109
:raises: BzrError if the parents are not known.
111
raise NotImplementedError(self.get_parent_ids)
113
def has_filename(self, filename):
114
"""True if the tree has given filename."""
115
raise NotImplementedError()
117
def has_id(self, file_id):
118
file_id = osutils.safe_file_id(file_id)
119
return self.inventory.has_id(file_id)
121
__contains__ = has_id
123
def has_or_had_id(self, file_id):
124
file_id = osutils.safe_file_id(file_id)
125
if file_id == self.inventory.root.file_id:
127
return self.inventory.has_id(file_id)
130
return iter(self.inventory)
132
def id2path(self, file_id):
133
file_id = osutils.safe_file_id(file_id)
134
return self.inventory.id2path(file_id)
136
def is_control_filename(self, filename):
137
"""True if filename is the name of a control file in this tree.
139
:param filename: A filename within the tree. This is a relative path
140
from the root of this tree.
142
This is true IF and ONLY IF the filename is part of the meta data
143
that bzr controls in this tree. I.E. a random .bzr directory placed
144
on disk will not be a control file for this tree.
146
return self.bzrdir.is_control_filename(filename)
149
def iter_entries_by_dir(self, specific_file_ids=None):
150
"""Walk the tree in 'by_dir' order.
152
This will yield each entry in the tree as a (path, entry) tuple. The
153
order that they are yielded is: the contents of a directory are
154
preceeded by the parent of a directory, and all the contents of a
155
directory are grouped together.
157
return self.inventory.iter_entries_by_dir(
158
specific_file_ids=specific_file_ids)
160
def kind(self, file_id):
161
raise NotImplementedError("subclasses must implement kind")
163
def _comparison_data(self, entry, path):
164
"""Return a tuple of kind, executable, stat_value for a file.
166
entry may be None if there is no inventory entry for the file, but
167
path must always be supplied.
169
kind is None if there is no file present (even if an inventory id is
170
present). executable is False for non-file entries.
172
raise NotImplementedError(self._comparison_data)
174
def _file_size(self, entry, stat_value):
175
raise NotImplementedError(self._file_size)
177
def _get_inventory(self):
178
return self._inventory
180
def get_file(self, file_id):
181
"""Return a file object for the file file_id in the tree."""
182
raise NotImplementedError(self.get_file)
184
def get_file_mtime(self, file_id, path=None):
185
"""Return the modification time for a file.
187
:param file_id: The handle for this file.
188
:param path: The path that this file can be found at.
189
These must point to the same object.
191
raise NotImplementedError(self.get_file_mtime)
193
def get_file_by_path(self, path):
194
return self.get_file(self._inventory.path2id(path))
196
def get_symlink_target(self, file_id):
197
"""Get the target for a given file_id.
199
It is assumed that the caller already knows that file_id is referencing
201
:param file_id: Handle for the symlink entry.
202
:return: The path the symlink points to.
204
raise NotImplementedError(self.get_symlink_target)
206
def annotate_iter(self, file_id):
207
"""Return an iterator of revision_id, line tuples
209
For working trees (and mutable trees in general), the special
210
revision_id 'current:' will be used for lines that are new in this
211
tree, e.g. uncommitted changes.
212
:param file_id: The file to produce an annotated version from
214
raise NotImplementedError(self.annotate_iter)
216
inventory = property(_get_inventory,
217
doc="Inventory of this Tree")
219
def _check_retrieved(self, ie, f):
222
fp = fingerprint_file(f)
225
if ie.text_size is not None:
226
if ie.text_size != fp['size']:
227
raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
228
["inventory expects %d bytes" % ie.text_size,
229
"file is actually %d bytes" % fp['size'],
230
"store is probably damaged/corrupt"])
232
if ie.text_sha1 != fp['sha1']:
233
raise BzrError("wrong SHA-1 for file %r in %r" % (ie.file_id, self._store),
234
["inventory expects %s" % ie.text_sha1,
235
"file is actually %s" % fp['sha1'],
236
"store is probably damaged/corrupt"])
238
def path2id(self, path):
239
"""Return the id for path in this tree."""
240
return self._inventory.path2id(path)
242
def paths2ids(self, paths, trees=[], require_versioned=True):
243
"""Return all the ids that can be reached by walking from paths.
245
Each path is looked up in each this tree and any extras provided in
246
trees, and this is repeated recursively: the children in an extra tree
247
of a directory that has been renamed under a provided path in this tree
248
are all returned, even if none exist until a provided path in this
249
tree, and vice versa.
251
:param paths: An iterable of paths to start converting to ids from.
252
Alternatively, if paths is None, no ids should be calculated and None
253
will be returned. This is offered to make calling the api unconditional
254
for code that *might* take a list of files.
255
:param trees: Additional trees to consider.
256
:param require_versioned: If False, do not raise NotVersionedError if
257
an element of paths is not versioned in this tree and all of trees.
259
return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
261
def print_file(self, file_id):
262
"""Print file with id `file_id` to stdout."""
263
file_id = osutils.safe_file_id(file_id)
265
sys.stdout.write(self.get_file_text(file_id))
270
def revision_tree(self, revision_id):
271
"""Obtain a revision tree for the revision revision_id.
273
The intention of this method is to allow access to possibly cached
274
tree data. Implementors of this method should raise NoSuchRevision if
275
the tree is not locally available, even if they could obtain the
276
tree via a repository or some other means. Callers are responsible
277
for finding the ultimate source for a revision tree.
279
:param revision_id: The revision_id of the requested tree.
281
:raises: NoSuchRevision if the tree cannot be obtained.
283
raise errors.NoSuchRevisionInTree(self, revision_id)
286
"""What files are present in this tree and unknown.
288
:return: an iterator over the unknown files.
295
def filter_unversioned_files(self, paths):
296
"""Filter out paths that are versioned.
298
:return: set of paths.
300
# NB: we specifically *don't* call self.has_filename, because for
301
# WorkingTrees that can indicate files that exist on disk but that
303
pred = self.inventory.has_filename
304
return set((p for p in paths if not pred(p)))
306
def walkdirs(self, prefix=""):
307
"""Walk the contents of this tree from path down.
309
This yields all the data about the contents of a directory at a time.
310
After each directory has been yielded, if the caller has mutated the
311
list to exclude some directories, they are then not descended into.
313
The data yielded is of the form:
314
((directory-relpath, directory-path-from-root, directory-fileid),
315
[(relpath, basename, kind, lstat, path_from_tree_root, file_id,
316
versioned_kind), ...]),
317
- directory-relpath is the containing dirs relpath from prefix
318
- directory-path-from-root is the containing dirs path from /
319
- directory-fileid is the id of the directory if it is versioned.
320
- relpath is the relative path within the subtree being walked.
321
- basename is the basename
322
- kind is the kind of the file now. If unknonwn then the file is not
323
present within the tree - but it may be recorded as versioned. See
325
- lstat is the stat data *if* the file was statted.
326
- path_from_tree_root is the path from the root of the tree.
327
- file_id is the file_id is the entry is versioned.
328
- versioned_kind is the kind of the file as last recorded in the
329
versioning system. If 'unknown' the file is not versioned.
330
One of 'kind' and 'versioned_kind' must not be 'unknown'.
332
:param prefix: Start walking from prefix within the tree rather than
333
at the root. This allows one to walk a subtree but get paths that are
334
relative to a tree rooted higher up.
335
:return: an iterator over the directory data.
337
raise NotImplementedError(self.walkdirs)
340
class EmptyTree(Tree):
343
self._inventory = Inventory(root_id=None)
344
symbol_versioning.warn('EmptyTree is deprecated as of bzr 0.9 please'
345
' use repository.revision_tree instead.',
346
DeprecationWarning, stacklevel=2)
348
def get_parent_ids(self):
351
def get_symlink_target(self, file_id):
354
def has_filename(self, filename):
357
def kind(self, file_id):
358
file_id = osutils.safe_file_id(file_id)
359
assert self._inventory[file_id].kind == "directory"
362
def list_files(self, include_root=False):
365
def __contains__(self, file_id):
366
file_id = osutils.safe_file_id(file_id)
367
return (file_id in self._inventory)
369
def get_file_sha1(self, file_id, path=None, stat_value=None):
373
######################################################################
376
# TODO: Merge these two functions into a single one that can operate
377
# on either a whole tree or a set of files.
379
# TODO: Return the diff in order by filename, not by category or in
380
# random order. Can probably be done by lock-stepping through the
381
# filenames from both trees.
384
def file_status(filename, old_tree, new_tree):
385
"""Return single-letter status, old and new names for a file.
387
The complexity here is in deciding how to represent renames;
388
many complex cases are possible.
390
old_inv = old_tree.inventory
391
new_inv = new_tree.inventory
392
new_id = new_inv.path2id(filename)
393
old_id = old_inv.path2id(filename)
395
if not new_id and not old_id:
396
# easy: doesn't exist in either; not versioned at all
397
if new_tree.is_ignored(filename):
398
return 'I', None, None
400
return '?', None, None
402
# There is now a file of this name, great.
405
# There is no longer a file of this name, but we can describe
406
# what happened to the file that used to have
407
# this name. There are two possibilities: either it was
408
# deleted entirely, or renamed.
410
if new_inv.has_id(old_id):
411
return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
413
return 'D', old_inv.id2path(old_id), None
415
# if the file_id is new in this revision, it is added
416
if new_id and not old_inv.has_id(new_id):
419
# if there used to be a file of this name, but that ID has now
420
# disappeared, it is deleted
421
if old_id and not new_inv.has_id(old_id):
428
def find_renames(old_inv, new_inv):
429
for file_id in old_inv:
430
if file_id not in new_inv:
432
old_name = old_inv.id2path(file_id)
433
new_name = new_inv.id2path(file_id)
434
if old_name != new_name:
435
yield (old_name, new_name)
438
def find_ids_across_trees(filenames, trees, require_versioned=True):
439
"""Find the ids corresponding to specified filenames.
441
All matches in all trees will be used, and all children of matched
442
directories will be used.
444
:param filenames: The filenames to find file_ids for (if None, returns
446
:param trees: The trees to find file_ids within
447
:param require_versioned: if true, all specified filenames must occur in
449
:return: a set of file ids for the specified filenames and their children.
453
specified_path_ids = _find_ids_across_trees(filenames, trees,
455
return _find_children_across_trees(specified_path_ids, trees)
458
def _find_ids_across_trees(filenames, trees, require_versioned):
459
"""Find the ids corresponding to specified filenames.
461
All matches in all trees will be used, but subdirectories are not scanned.
463
:param filenames: The filenames to find file_ids for
464
:param trees: The trees to find file_ids within
465
:param require_versioned: if true, all specified filenames must occur in
467
:return: a set of (path, file ids) for the specified filenames
470
interesting_ids = set()
471
for tree_path in filenames:
474
file_id = tree.path2id(tree_path)
475
if file_id is not None:
476
interesting_ids.add(file_id)
479
not_versioned.append(tree_path)
480
if len(not_versioned) > 0 and require_versioned:
481
raise errors.PathsNotVersionedError(not_versioned)
482
return interesting_ids
485
def _find_children_across_trees(specified_ids, trees):
486
"""Return a set including specified ids and their children
488
All matches in all trees will be used.
490
:param trees: The trees to find file_ids within
491
:return: a set containing all specified ids and their children
493
interesting_ids = set(specified_ids)
494
pending = interesting_ids
495
# now handle children of interesting ids
496
# we loop so that we handle all children of each id in both trees
497
while len(pending) > 0:
499
for file_id in pending:
501
if not tree.has_id(file_id):
503
entry = tree.inventory[file_id]
504
for child in getattr(entry, 'children', {}).itervalues():
505
if child.file_id not in interesting_ids:
506
new_pending.add(child.file_id)
507
interesting_ids.update(new_pending)
508
pending = new_pending
509
return interesting_ids
512
class InterTree(InterObject):
513
"""This class represents operations taking place between two Trees.
515
Its instances have methods like 'compare' and contain references to the
516
source and target trees these operations are to be carried out on.
518
clients of bzrlib should not need to use InterTree directly, rather they
519
should use the convenience methods on Tree such as 'Tree.compare()' which
520
will pass through to InterTree as appropriate.
526
def compare(self, want_unchanged=False, specific_files=None,
527
extra_trees=None, require_versioned=False, include_root=False):
528
"""Return the changes from source to target.
530
:return: A TreeDelta.
531
:param specific_files: An optional list of file paths to restrict the
532
comparison to. When mapping filenames to ids, all matches in all
533
trees (including optional extra_trees) are used, and all children of
534
matched directories are included.
535
:param want_unchanged: An optional boolean requesting the inclusion of
536
unchanged entries in the result.
537
:param extra_trees: An optional list of additional trees to use when
538
mapping the contents of specific_files (paths) to file_ids.
539
:param require_versioned: An optional boolean (defaults to False). When
540
supplied and True all the 'specific_files' must be versioned, or
541
a PathsNotVersionedError will be thrown.
543
# NB: show_status depends on being able to pass in non-versioned files
544
# and report them as unknown
545
trees = (self.source,)
546
if extra_trees is not None:
547
trees = trees + tuple(extra_trees)
548
# target is usually the newer tree:
549
specific_file_ids = self.target.paths2ids(specific_files, trees,
550
require_versioned=require_versioned)
551
if specific_files and not specific_file_ids:
552
# All files are unversioned, so just return an empty delta
553
# _compare_trees would think we want a complete delta
554
return delta.TreeDelta()
555
return delta._compare_trees(self.source, self.target, want_unchanged,
556
specific_files, include_root, extra_trees=extra_trees)
558
def _iter_changes(self, include_unchanged=False,
559
specific_files=None, pb=None, extra_trees=[],
560
require_versioned=True):
561
"""Generate an iterator of changes between trees.
564
(file_id, path, changed_content, versioned, parent, name, kind,
567
Path is relative to the target tree. changed_content is True if the
568
file's content has changed. This includes changes to its kind, and to
571
versioned, parent, name, kind, executable are tuples of (from, to).
572
If a file is missing in a tree, its kind is None.
574
Iteration is done in parent-to-child order, relative to the target
577
There is no guarantee that all paths are in sorted order: the
578
requirement to expand the search due to renames may result in children
579
that should be found early being found late in the search, after
580
lexically later results have been returned.
581
:param require_versioned: Raise errors.PathsNotVersionedError if a
582
path in the specific_files list is not versioned in one of
583
source, target or extra_trees.
585
lookup_trees = [self.source]
587
lookup_trees.extend(extra_trees)
588
specific_file_ids = self.target.paths2ids(specific_files,
589
lookup_trees, require_versioned=require_versioned)
591
from_entries_by_dir = list(self.source.inventory.iter_entries_by_dir(
592
specific_file_ids=specific_file_ids))
593
from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
594
to_entries_by_dir = list(self.target.inventory.iter_entries_by_dir(
595
specific_file_ids=specific_file_ids))
596
num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
598
for to_path, to_entry in to_entries_by_dir:
599
file_id = to_entry.file_id
600
to_paths[file_id] = to_path
602
changed_content = False
603
from_path, from_entry = from_data.get(file_id, (None, None))
604
from_versioned = (from_entry is not None)
605
if from_entry is not None:
606
from_versioned = True
607
from_name = from_entry.name
608
from_parent = from_entry.parent_id
609
from_kind, from_executable, from_stat = \
610
self.source._comparison_data(from_entry, from_path)
613
from_versioned = False
617
from_executable = None
618
versioned = (from_versioned, True)
619
to_kind, to_executable, to_stat = \
620
self.target._comparison_data(to_entry, to_path)
621
kind = (from_kind, to_kind)
622
if kind[0] != kind[1]:
623
changed_content = True
624
elif from_kind == 'file':
625
from_size = self.source._file_size(from_entry, from_stat)
626
to_size = self.target._file_size(to_entry, to_stat)
627
if from_size != to_size:
628
changed_content = True
629
elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
630
self.target.get_file_sha1(file_id, to_path, to_stat)):
631
changed_content = True
632
elif from_kind == 'symlink':
633
if (self.source.get_symlink_target(file_id) !=
634
self.target.get_symlink_target(file_id)):
635
changed_content = True
636
parent = (from_parent, to_entry.parent_id)
637
name = (from_name, to_entry.name)
638
executable = (from_executable, to_executable)
640
pb.update('comparing files', entry_count, num_entries)
641
if (changed_content is not False or versioned[0] != versioned[1]
642
or parent[0] != parent[1] or name[0] != name[1] or
643
executable[0] != executable[1] or include_unchanged):
644
yield (file_id, to_path, changed_content, versioned, parent,
645
name, kind, executable)
647
def get_to_path(from_entry):
648
if from_entry.parent_id is None:
651
if from_entry.parent_id not in to_paths:
652
get_to_path(self.source.inventory[from_entry.parent_id])
653
to_path = osutils.pathjoin(to_paths[from_entry.parent_id],
655
to_paths[from_entry.file_id] = to_path
658
for path, from_entry in from_entries_by_dir:
659
file_id = from_entry.file_id
660
if file_id in to_paths:
662
to_path = get_to_path(from_entry)
665
pb.update('comparing files', entry_count, num_entries)
666
versioned = (True, False)
667
parent = (from_entry.parent_id, None)
668
name = (from_entry.name, None)
669
from_kind, from_executable, stat_value = \
670
self.source._comparison_data(from_entry, path)
671
kind = (from_kind, None)
672
executable = (from_executable, None)
673
changed_content = True
674
# the parent's path is necessarily known at this point.
675
yield(file_id, to_path, changed_content, versioned, parent,
676
name, kind, executable)
679
# This was deprecated before 0.12, but did not have an official warning
680
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
681
def RevisionTree(*args, **kwargs):
682
"""RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
684
Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
687
from bzrlib.revisiontree import RevisionTree as _RevisionTree
688
return _RevisionTree(*args, **kwargs)
added
removed
bzrlib/tree.py
