/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

(broken) merge aaron's workingtree format changes

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
1
# Copyright (C) 2005 Canonical Ltd
2
 
 
 
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
 
 
7
#
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
12
 
 
 
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
18
"""
19
19
 
20
20
import os
 
21
from cStringIO import StringIO
21
22
 
22
23
import bzrlib
 
24
from bzrlib import (
 
25
    delta,
 
26
    osutils,
 
27
    symbol_versioning,
 
28
    )
 
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
23
36
from bzrlib.trace import mutter, note
24
 
from bzrlib.errors import BzrError
25
 
from bzrlib.inventory import Inventory
26
 
from bzrlib.osutils import pumpfile, appendpath, fingerprint_file
27
 
 
28
 
 
29
 
exporters = {}
 
37
 
30
38
 
31
39
class Tree(object):
32
40
    """Abstract file tree.
37
45
 
38
46
    * `RevisionTree` is a tree as recorded at some point in the past.
39
47
 
40
 
    * `EmptyTree`
41
 
 
42
48
    Trees contain an `Inventory` object, and also know how to retrieve
43
49
    file texts mentioned in the inventory, either from a working
44
50
    directory or from a store.
50
56
    trees or versioned trees.
51
57
    """
52
58
    
 
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.
 
62
 
 
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.
 
75
 
 
76
        The comparison will be performed by an InterTree object looked up on 
 
77
        self and other.
 
78
        """
 
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
 
88
            )
 
89
 
 
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)
 
96
    
 
97
    def conflicts(self):
 
98
        """Get a list of the conflicts in the tree.
 
99
 
 
100
        Each conflict is an instance of bzrlib.conflicts.Conflict.
 
101
        """
 
102
        return []
 
103
 
 
104
    def get_parent_ids(self):
 
105
        """Get the parent ids for this tree. 
 
106
 
 
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.
 
110
        """
 
111
        raise NotImplementedError(self.get_parent_ids)
 
112
    
53
113
    def has_filename(self, filename):
54
114
        """True if the tree has given filename."""
55
115
        raise NotImplementedError()
56
116
 
57
117
    def has_id(self, file_id):
 
118
        file_id = osutils.safe_file_id(file_id)
58
119
        return self.inventory.has_id(file_id)
59
120
 
60
121
    __contains__ = has_id
61
122
 
 
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:
 
126
            return True
 
127
        return self.inventory.has_id(file_id)
 
128
 
62
129
    def __iter__(self):
63
130
        return iter(self.inventory)
64
131
 
65
132
    def id2path(self, file_id):
 
133
        file_id = osutils.safe_file_id(file_id)
66
134
        return self.inventory.id2path(file_id)
67
135
 
 
136
    def is_control_filename(self, filename):
 
137
        """True if filename is the name of a control file in this tree.
 
138
        
 
139
        :param filename: A filename within the tree. This is a relative path
 
140
        from the root of this tree.
 
141
 
 
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.
 
145
        """
 
146
        return self.bzrdir.is_control_filename(filename)
 
147
 
 
148
    @needs_read_lock
 
149
    def iter_entries_by_dir(self, specific_file_ids=None):
 
150
        """Walk the tree in 'by_dir' order.
 
151
 
 
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.
 
156
        """
 
157
        return self.inventory.iter_entries_by_dir(
 
158
            specific_file_ids=specific_file_ids)
 
159
 
 
160
    def iter_reference_entries(self):
 
161
        for path, entry in self.iter_entries_by_dir():
 
162
            if entry.kind == 'tree-reference':
 
163
                yield path, entry
 
164
 
 
165
    def kind(self, file_id):
 
166
        raise NotImplementedError("subclasses must implement kind")
 
167
 
 
168
    def get_reference_revision(self, entry, path=None):
 
169
        raise NotImplementedError("subclasses must implement "
 
170
                                  "get_reference_revision")
 
171
 
 
172
    def _comparison_data(self, entry, path):
 
173
        """Return a tuple of kind, executable, stat_value for a file.
 
174
 
 
175
        entry may be None if there is no inventory entry for the file, but
 
176
        path must always be supplied.
 
177
 
 
178
        kind is None if there is no file present (even if an inventory id is
 
179
        present).  executable is False for non-file entries.
 
180
        """
 
181
        raise NotImplementedError(self._comparison_data)
 
182
 
 
183
    def _file_size(self, entry, stat_value):
 
184
        raise NotImplementedError(self._file_size)
 
185
 
68
186
    def _get_inventory(self):
69
187
        return self._inventory
70
188
    
 
189
    def get_file(self, file_id):
 
190
        """Return a file object for the file file_id in the tree."""
 
191
        raise NotImplementedError(self.get_file)
 
192
    
71
193
    def get_file_by_path(self, path):
72
194
        return self.get_file(self._inventory.path2id(path))
73
195
 
 
196
    def get_symlink_target(self, file_id):
 
197
        """Get the target for a given file_id.
 
198
 
 
199
        It is assumed that the caller already knows that file_id is referencing
 
200
        a symlink.
 
201
        :param file_id: Handle for the symlink entry.
 
202
        :return: The path the symlink points to.
 
203
        """
 
204
        raise NotImplementedError(self.get_symlink_target)
 
205
 
 
206
    def annotate_iter(self, file_id):
 
207
        """Return an iterator of revision_id, line tuples
 
208
 
 
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
 
213
        """
 
214
        raise NotImplementedError(self.annotate_iter)
 
215
 
74
216
    inventory = property(_get_inventory,
75
217
                         doc="Inventory of this Tree")
76
218
 
77
219
    def _check_retrieved(self, ie, f):
 
220
        if not __debug__:
 
221
            return  
78
222
        fp = fingerprint_file(f)
79
223
        f.seek(0)
80
224
        
81
 
        if ie.text_size != None:
 
225
        if ie.text_size is not None:
82
226
            if ie.text_size != fp['size']:
83
227
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
84
228
                        ["inventory expects %d bytes" % ie.text_size,
91
235
                     "file is actually %s" % fp['sha1'],
92
236
                     "store is probably damaged/corrupt"])
93
237
 
94
 
 
95
 
    def print_file(self, fileid):
96
 
        """Print file with id `fileid` to stdout."""
 
238
    def path2id(self, path):
 
239
        """Return the id for path in this tree."""
 
240
        return self._inventory.path2id(path)
 
241
 
 
242
    def paths2ids(self, paths, trees=[], require_versioned=True):
 
243
        """Return all the ids that can be reached by walking from paths.
 
244
        
 
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.
 
250
 
 
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.
 
258
        """
 
259
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
 
260
 
 
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)
97
264
        import sys
98
 
        pumpfile(self.get_file(fileid), sys.stdout)
99
 
        
100
 
        
101
 
    def export(self, dest, format='dir', root=None):
102
 
        """Export this tree."""
103
 
        try:
104
 
            exporter = exporters[format]
105
 
        except KeyError:
106
 
            from bzrlib.errors import BzrCommandError
107
 
            raise BzrCommandError("export format %r not supported" % format)
108
 
        exporter(self, dest, root)
109
 
 
110
 
 
111
 
 
112
 
class RevisionTree(Tree):
113
 
    """Tree viewing a previous revision.
114
 
 
115
 
    File text can be retrieved from the text store.
116
 
 
117
 
    TODO: Some kind of `__repr__` method, but a good one
118
 
           probably means knowing the branch and revision number,
119
 
           or at least passing a description to the constructor.
120
 
    """
121
 
    
122
 
    def __init__(self, store, inv):
123
 
        self._store = store
124
 
        self._inventory = inv
125
 
 
126
 
    def get_file(self, file_id):
127
 
        ie = self._inventory[file_id]
128
 
        f = self._store[ie.text_id]
129
 
        mutter("  get fileid{%s} from %r" % (file_id, self))
130
 
        self._check_retrieved(ie, f)
131
 
        return f
132
 
 
133
 
    def get_file_size(self, file_id):
134
 
        return self._inventory[file_id].text_size
135
 
 
136
 
    def get_file_sha1(self, file_id):
137
 
        ie = self._inventory[file_id]
138
 
        return ie.text_sha1
139
 
 
140
 
    def has_filename(self, filename):
141
 
        return bool(self.inventory.path2id(filename))
142
 
 
143
 
    def list_files(self):
144
 
        # The only files returned by this are those from the version
145
 
        for path, entry in self.inventory.iter_entries():
146
 
            yield path, 'V', entry.kind, entry.file_id
 
265
        sys.stdout.write(self.get_file_text(file_id))
 
266
 
 
267
    def lock_read(self):
 
268
        pass
 
269
 
 
270
    def revision_tree(self, revision_id):
 
271
        """Obtain a revision tree for the revision revision_id.
 
272
 
 
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.
 
278
 
 
279
        :param revision_id: The revision_id of the requested tree.
 
280
        :return: A Tree.
 
281
        :raises: NoSuchRevision if the tree cannot be obtained.
 
282
        """
 
283
        raise errors.NoSuchRevisionInTree(self, revision_id)
 
284
 
 
285
    def unknowns(self):
 
286
        """What files are present in this tree and unknown.
 
287
        
 
288
        :return: an iterator over the unknown files.
 
289
        """
 
290
        return iter([])
 
291
 
 
292
    def unlock(self):
 
293
        pass
 
294
 
 
295
    def filter_unversioned_files(self, paths):
 
296
        """Filter out paths that are not versioned.
 
297
 
 
298
        :return: set of paths.
 
299
        """
 
300
        # NB: we specifically *don't* call self.has_filename, because for
 
301
        # WorkingTrees that can indicate files that exist on disk but that 
 
302
        # are not versioned.
 
303
        pred = self.inventory.has_filename
 
304
        return set((p for p in paths if not pred(p)))
 
305
 
 
306
    def walkdirs(self, prefix=""):
 
307
        """Walk the contents of this tree from path down.
 
308
 
 
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.
 
312
        
 
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
 
324
           versioned_kind.
 
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'.
 
331
 
 
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.
 
336
        """
 
337
        raise NotImplementedError(self.walkdirs)
147
338
 
148
339
 
149
340
class EmptyTree(Tree):
 
341
 
150
342
    def __init__(self):
151
 
        self._inventory = Inventory()
 
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)
 
347
 
 
348
    def get_parent_ids(self):
 
349
        return []
 
350
 
 
351
    def get_symlink_target(self, file_id):
 
352
        return None
152
353
 
153
354
    def has_filename(self, filename):
154
355
        return False
155
356
 
156
 
    def list_files(self):
157
 
        if False:  # just to make it a generator
158
 
            yield None
 
357
    def kind(self, file_id):
 
358
        file_id = osutils.safe_file_id(file_id)
 
359
        assert self._inventory[file_id].kind == "directory"
 
360
        return "directory"
 
361
 
 
362
    def list_files(self, include_root=False):
 
363
        return iter([])
159
364
    
 
365
    def __contains__(self, file_id):
 
366
        file_id = osutils.safe_file_id(file_id)
 
367
        return (file_id in self._inventory)
 
368
 
 
369
    def get_file_sha1(self, file_id, path=None, stat_value=None):
 
370
        return None
160
371
 
161
372
 
162
373
######################################################################
224
435
            yield (old_name, new_name)
225
436
            
226
437
 
227
 
 
228
 
######################################################################
229
 
# export
230
 
 
231
 
def dir_exporter(tree, dest, root):
232
 
    """Export this tree to a new directory.
233
 
 
234
 
    `dest` should not exist, and will be created holding the
235
 
    contents of this tree.
236
 
 
237
 
    TODO: To handle subdirectories we need to create the
238
 
           directories first.
239
 
 
240
 
    :note: If the export fails, the destination directory will be
241
 
           left in a half-assed state.
242
 
    """
243
 
    import os
244
 
    os.mkdir(dest)
245
 
    mutter('export version %r' % tree)
246
 
    inv = tree.inventory
247
 
    for dp, ie in inv.iter_entries():
248
 
        kind = ie.kind
249
 
        fullpath = appendpath(dest, dp)
250
 
        if kind == 'directory':
251
 
            os.mkdir(fullpath)
252
 
        elif kind == 'file':
253
 
            pumpfile(tree.get_file(ie.file_id), file(fullpath, 'wb'))
254
 
        else:
255
 
            raise BzrError("don't know how to export {%s} of kind %r" % (ie.file_id, kind))
256
 
        mutter("  export {%s} kind %s to %s" % (ie.file_id, kind, fullpath))
257
 
exporters['dir'] = dir_exporter
258
 
 
259
 
try:
260
 
    import tarfile
261
 
except ImportError:
262
 
    pass
263
 
else:
264
 
    def get_root_name(dest):
265
 
        """Get just the root name for a tarball.
266
 
 
267
 
        >>> get_root_name('mytar.tar')
268
 
        'mytar'
269
 
        >>> get_root_name('mytar.tar.bz2')
270
 
        'mytar'
271
 
        >>> get_root_name('tar.tar.tar.tgz')
272
 
        'tar.tar.tar'
273
 
        >>> get_root_name('bzr-0.0.5.tar.gz')
274
 
        'bzr-0.0.5'
275
 
        >>> get_root_name('a/long/path/mytar.tgz')
276
 
        'mytar'
277
 
        >>> get_root_name('../parent/../dir/other.tbz2')
278
 
        'other'
279
 
        """
280
 
        endings = ['.tar', '.tar.gz', '.tgz', '.tar.bz2', '.tbz2']
281
 
        dest = os.path.basename(dest)
282
 
        for end in endings:
283
 
            if dest.endswith(end):
284
 
                return dest[:-len(end)]
285
 
 
286
 
    def tar_exporter(tree, dest, root, compression=None):
287
 
        """Export this tree to a new tar file.
288
 
 
289
 
        `dest` will be created holding the contents of this tree; if it
290
 
        already exists, it will be clobbered, like with "tar -c".
291
 
        """
292
 
        from time import time
293
 
        now = time()
294
 
        compression = str(compression or '')
295
 
        if root is None:
296
 
            root = get_root_name(dest)
297
 
        try:
298
 
            ball = tarfile.open(dest, 'w:' + compression)
299
 
        except tarfile.CompressionError, e:
300
 
            raise BzrError(str(e))
301
 
        mutter('export version %r' % tree)
302
 
        inv = tree.inventory
303
 
        for dp, ie in inv.iter_entries():
304
 
            mutter("  export {%s} kind %s to %s" % (ie.file_id, ie.kind, dest))
305
 
            item = tarfile.TarInfo(os.path.join(root, dp))
306
 
            # TODO: would be cool to actually set it to the timestamp of the
307
 
            # revision it was last changed
308
 
            item.mtime = now
309
 
            if ie.kind == 'directory':
310
 
                item.type = tarfile.DIRTYPE
311
 
                fileobj = None
312
 
                item.name += '/'
313
 
                item.size = 0
314
 
                item.mode = 0755
315
 
            elif ie.kind == 'file':
316
 
                item.type = tarfile.REGTYPE
317
 
                fileobj = tree.get_file(ie.file_id)
318
 
                item.size = _find_file_size(fileobj)
319
 
                item.mode = 0644
320
 
            else:
321
 
                raise BzrError("don't know how to export {%s} of kind %r" %
322
 
                        (ie.file_id, ie.kind))
323
 
 
324
 
            ball.addfile(item, fileobj)
325
 
        ball.close()
326
 
    exporters['tar'] = tar_exporter
327
 
 
328
 
    def tgz_exporter(tree, dest, root):
329
 
        tar_exporter(tree, dest, root, compression='gz')
330
 
    exporters['tgz'] = tgz_exporter
331
 
 
332
 
    def tbz_exporter(tree, dest, root):
333
 
        tar_exporter(tree, dest, root, compression='bz2')
334
 
    exporters['tbz2'] = tbz_exporter
335
 
 
336
 
 
337
 
def _find_file_size(fileobj):
338
 
    offset = fileobj.tell()
339
 
    try:
340
 
        fileobj.seek(0, 2)
341
 
        size = fileobj.tell()
342
 
    except TypeError:
343
 
        # gzip doesn't accept second argument to seek()
344
 
        fileobj.seek(0)
345
 
        size = 0
346
 
        while True:
347
 
            nread = len(fileobj.read())
348
 
            if nread == 0:
349
 
                break
350
 
            size += nread
351
 
    fileobj.seek(offset)
352
 
    return size
 
438
def find_ids_across_trees(filenames, trees, require_versioned=True):
 
439
    """Find the ids corresponding to specified filenames.
 
440
    
 
441
    All matches in all trees will be used, and all children of matched
 
442
    directories will be used.
 
443
 
 
444
    :param filenames: The filenames to find file_ids for (if None, returns
 
445
        None)
 
446
    :param trees: The trees to find file_ids within
 
447
    :param require_versioned: if true, all specified filenames must occur in
 
448
    at least one tree.
 
449
    :return: a set of file ids for the specified filenames and their children.
 
450
    """
 
451
    if not filenames:
 
452
        return None
 
453
    specified_path_ids = _find_ids_across_trees(filenames, trees,
 
454
        require_versioned)
 
455
    return _find_children_across_trees(specified_path_ids, trees)
 
456
#    specified_ids = [id for path, id in _find_path_ids_across_trees(filenames, trees, require_versioned)]
 
457
#    return _find_children_across_trees(specified_ids, trees)
 
458
 
 
459
def find_path_ids_across_trees(filenames, trees, require_versioned=True):
 
460
    """Find the paths and ids corresponding to specified filenames.
 
461
    
 
462
    All matches in all trees will be used, and all children of matched
 
463
    directories will be included
 
464
 
 
465
    :param filenames: The filenames to find file_ids for
 
466
    :param trees: The trees to find file_ids within
 
467
    :param require_versioned: if true, all specified filenames must occur in
 
468
        at least one tree.
 
469
    :return: a set of (path, file ids) for the specified filenames and their
 
470
        children. The returned path is the path of the id in the first tree
 
471
        that contains it. This matters when files have been moved 
 
472
    """
 
473
    if not filenames:
 
474
        return set()
 
475
    # This function needs to know the ids for filenames in all trees, then
 
476
    # search for those same files and children in all the other trees.
 
477
    # it is complicated by the same path in two trees being able to have
 
478
    # different ids, which might both be present in both trees.
 
479
    # consider two trees, which have had 'mv foo bar' and 'mv baz foo' done
 
480
    # in this case, a diff of 'foo' should should changes to both the current
 
481
    # 'bar' and the current 'foo' which was baz. Its arguable that if 
 
482
    # the situation is 'mv parent/foo bar' and 'mv baz parent/foo', that 
 
483
    # we should return the current bar and the current parent/foo' - at the 
 
484
    # moment we do, but we loop around all ids and all trees: I*T checks.
 
485
    
 
486
    # Updating this algorithm to be fast in the common case:
 
487
    # nothing has moved, all files have the same id in parent, child and there
 
488
    # are only two trees (or one is working tree and the others are parents).
 
489
    # walk the dirstate. as we find each path, gather the paths of that
 
490
    # id in all trees. add a mapping from the id to the path in those trees.
 
491
    # now lookup children by id, again in all trees; for these trees that
 
492
    # nothing has moved in, the id->path mapping will allow us to find the
 
493
    # parent trivially. To answer 'has anything been moved' in one of the
 
494
    # dirstate parent trees though, we will need to stare harder at it.
 
495
 
 
496
    #  Now, given a path index, that is trivial for any one tree, and given
 
497
    #  that we can ask for additional data from a dirstate tree, its a single
 
498
    #  pass, though it will require scanning the entire tree to find paths
 
499
    #  that were at the current location.
 
500
    # ideal results?: There are three things: tree, path, id. Pathologically
 
501
    # we can have completely disjoint ids for each tree; but we cannot have 
 
502
    # disjoin paths for each tree, except if we scan each tree for the 
 
503
    # different ids from other trees.
 
504
 
 
505
    specified_path_ids = _find_ids_across_trees(filenames, trees,
 
506
        require_versioned)
 
507
    return _find_path_id_children_across_trees(specified_path_ids, trees)
 
508
 
 
509
 
 
510
def _find_ids_across_trees(filenames, trees, require_versioned):
 
511
    """Find the ids corresponding to specified filenames.
 
512
    
 
513
    All matches in all trees will be used, but subdirectories are not scanned.
 
514
 
 
515
    :param filenames: The filenames to find file_ids for
 
516
    :param trees: The trees to find file_ids within
 
517
    :param require_versioned: if true, all specified filenames must occur in
 
518
        at least one tree.
 
519
    :return: a set of (path, file ids) for the specified filenames
 
520
    """
 
521
    not_versioned = []
 
522
    interesting_ids = set()
 
523
    for tree_path in filenames:
 
524
        not_found = True
 
525
        for tree in trees:
 
526
            file_id = tree.path2id(tree_path)
 
527
            if file_id is not None:
 
528
                interesting_ids.add(file_id)
 
529
                not_found = False
 
530
        if not_found:
 
531
            not_versioned.append(tree_path)
 
532
    if len(not_versioned) > 0 and require_versioned:
 
533
        raise errors.PathsNotVersionedError(not_versioned)
 
534
    return interesting_ids
 
535
 
 
536
 
 
537
def _find_children_across_trees(specified_ids, trees):
 
538
    """Return a set including specified ids and their children
 
539
    
 
540
    All matches in all trees will be used.
 
541
 
 
542
    :param trees: The trees to find file_ids within
 
543
    :return: a set containing all specified ids and their children 
 
544
    """
 
545
    interesting_ids = set(specified_ids)
 
546
    pending = interesting_ids
 
547
    # now handle children of interesting ids
 
548
    # we loop so that we handle all children of each id in both trees
 
549
    while len(pending) > 0:
 
550
        new_pending = set()
 
551
        for file_id in pending:
 
552
            for tree in trees:
 
553
                if not tree.has_id(file_id):
 
554
                    continue
 
555
                entry = tree.inventory[file_id]
 
556
                for child in getattr(entry, 'children', {}).itervalues():
 
557
                    if child.file_id not in interesting_ids:
 
558
                        new_pending.add(child.file_id)
 
559
        interesting_ids.update(new_pending)
 
560
        pending = new_pending
 
561
    return interesting_ids
 
562
 
 
563
 
 
564
class InterTree(InterObject):
 
565
    """This class represents operations taking place between two Trees.
 
566
 
 
567
    Its instances have methods like 'compare' and contain references to the
 
568
    source and target trees these operations are to be carried out on.
 
569
 
 
570
    clients of bzrlib should not need to use InterTree directly, rather they
 
571
    should use the convenience methods on Tree such as 'Tree.compare()' which
 
572
    will pass through to InterTree as appropriate.
 
573
    """
 
574
 
 
575
    _optimisers = []
 
576
 
 
577
    @needs_read_lock
 
578
    def compare(self, want_unchanged=False, specific_files=None,
 
579
        extra_trees=None, require_versioned=False, include_root=False):
 
580
        """Return the changes from source to target.
 
581
 
 
582
        :return: A TreeDelta.
 
583
        :param specific_files: An optional list of file paths to restrict the
 
584
            comparison to. When mapping filenames to ids, all matches in all
 
585
            trees (including optional extra_trees) are used, and all children of
 
586
            matched directories are included.
 
587
        :param want_unchanged: An optional boolean requesting the inclusion of
 
588
            unchanged entries in the result.
 
589
        :param extra_trees: An optional list of additional trees to use when
 
590
            mapping the contents of specific_files (paths) to file_ids.
 
591
        :param require_versioned: An optional boolean (defaults to False). When
 
592
            supplied and True all the 'specific_files' must be versioned, or
 
593
            a PathsNotVersionedError will be thrown.
 
594
        """
 
595
        # NB: show_status depends on being able to pass in non-versioned files
 
596
        # and report them as unknown
 
597
        trees = (self.source,)
 
598
        if extra_trees is not None:
 
599
            trees = trees + tuple(extra_trees)
 
600
        # target is usually the newer tree:
 
601
        specific_file_ids = self.target.paths2ids(specific_files, trees,
 
602
            require_versioned=require_versioned)
 
603
        if specific_files and not specific_file_ids:
 
604
            # All files are unversioned, so just return an empty delta
 
605
            # _compare_trees would think we want a complete delta
 
606
            return delta.TreeDelta()
 
607
        return delta._compare_trees(self.source, self.target, want_unchanged,
 
608
            specific_files, include_root, extra_trees=extra_trees)
 
609
 
 
610
    def _iter_changes(self, include_unchanged=False,
 
611
                      specific_files=None, pb=None, extra_trees=[],
 
612
                      require_versioned=True):
 
613
        """Generate an iterator of changes between trees.
 
614
 
 
615
        A tuple is returned:
 
616
        (file_id, path, changed_content, versioned, parent, name, kind,
 
617
         executable)
 
618
 
 
619
        Path is relative to the target tree.  changed_content is True if the
 
620
        file's content has changed.  This includes changes to its kind, and to
 
621
        a symlink's target.
 
622
 
 
623
        versioned, parent, name, kind, executable are tuples of (from, to).
 
624
        If a file is missing in a tree, its kind is None.
 
625
 
 
626
        Iteration is done in parent-to-child order, relative to the target
 
627
        tree.
 
628
 
 
629
        There is no guarantee that all paths are in sorted order: the
 
630
        requirement to expand the search due to renames may result in children
 
631
        that should be found early being found late in the search, after
 
632
        lexically later results have been returned.
 
633
        :param require_versioned: Raise errors.PathsNotVersionedError if a
 
634
            path in the specific_files list is not versioned in one of
 
635
            source, target or extra_trees.
 
636
        """
 
637
        lookup_trees = [self.source]
 
638
        if extra_trees:
 
639
             lookup_trees.extend(extra_trees)
 
640
        specific_file_ids = self.target.paths2ids(specific_files,
 
641
            lookup_trees, require_versioned=require_versioned)
 
642
        to_paths = {}
 
643
        from_entries_by_dir = list(self.source.inventory.iter_entries_by_dir(
 
644
            specific_file_ids=specific_file_ids))
 
645
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
 
646
        to_entries_by_dir = list(self.target.inventory.iter_entries_by_dir(
 
647
            specific_file_ids=specific_file_ids))
 
648
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
 
649
        entry_count = 0
 
650
        for to_path, to_entry in to_entries_by_dir:
 
651
            file_id = to_entry.file_id
 
652
            to_paths[file_id] = to_path
 
653
            entry_count += 1
 
654
            changed_content = False
 
655
            from_path, from_entry = from_data.get(file_id, (None, None))
 
656
            from_versioned = (from_entry is not None)
 
657
            if from_entry is not None:
 
658
                from_versioned = True
 
659
                from_name = from_entry.name
 
660
                from_parent = from_entry.parent_id
 
661
                from_kind, from_executable, from_stat = \
 
662
                    self.source._comparison_data(from_entry, from_path)
 
663
                entry_count += 1
 
664
            else:
 
665
                from_versioned = False
 
666
                from_kind = None
 
667
                from_parent = None
 
668
                from_name = None
 
669
                from_executable = None
 
670
            versioned = (from_versioned, True)
 
671
            to_kind, to_executable, to_stat = \
 
672
                self.target._comparison_data(to_entry, to_path)
 
673
            kind = (from_kind, to_kind)
 
674
            if kind[0] != kind[1]:
 
675
                changed_content = True
 
676
            elif from_kind == 'file':
 
677
                from_size = self.source._file_size(from_entry, from_stat)
 
678
                to_size = self.target._file_size(to_entry, to_stat)
 
679
                if from_size != to_size:
 
680
                    changed_content = True
 
681
                elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
 
682
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
 
683
                    changed_content = True
 
684
            elif from_kind == 'symlink':
 
685
                if (self.source.get_symlink_target(file_id) != 
 
686
                    self.target.get_symlink_target(file_id)):
 
687
                    changed_content = True
 
688
            elif from_kind == 'tree-reference':
 
689
                if (self.source.get_reference_revision(from_entry, from_path)
 
690
                    != self.target.get_reference_revision(to_entry, to_path)):
 
691
                    changed_content = True 
 
692
            parent = (from_parent, to_entry.parent_id)
 
693
            name = (from_name, to_entry.name)
 
694
            executable = (from_executable, to_executable)
 
695
            if pb is not None:
 
696
                pb.update('comparing files', entry_count, num_entries)
 
697
            if (changed_content is not False or versioned[0] != versioned[1] 
 
698
                or parent[0] != parent[1] or name[0] != name[1] or 
 
699
                executable[0] != executable[1] or include_unchanged):
 
700
                yield (file_id, to_path, changed_content, versioned, parent,
 
701
                       name, kind, executable)
 
702
 
 
703
        def get_to_path(from_entry):
 
704
            if from_entry.parent_id is None:
 
705
                to_path = ''
 
706
            else:
 
707
                if from_entry.parent_id not in to_paths:
 
708
                    get_to_path(self.source.inventory[from_entry.parent_id])
 
709
                to_path = osutils.pathjoin(to_paths[from_entry.parent_id],
 
710
                                           from_entry.name)
 
711
            to_paths[from_entry.file_id] = to_path
 
712
            return to_path
 
713
 
 
714
        for path, from_entry in from_entries_by_dir:
 
715
            file_id = from_entry.file_id
 
716
            if file_id in to_paths:
 
717
                continue
 
718
            to_path = get_to_path(from_entry)
 
719
            entry_count += 1
 
720
            if pb is not None:
 
721
                pb.update('comparing files', entry_count, num_entries)
 
722
            versioned = (True, False)
 
723
            parent = (from_entry.parent_id, None)
 
724
            name = (from_entry.name, None)
 
725
            from_kind, from_executable, stat_value = \
 
726
                self.source._comparison_data(from_entry, path)
 
727
            kind = (from_kind, None)
 
728
            executable = (from_executable, None)
 
729
            changed_content = True
 
730
            # the parent's path is necessarily known at this point.
 
731
            yield(file_id, to_path, changed_content, versioned, parent,
 
732
                  name, kind, executable)
 
733
 
 
734
 
 
735
# This was deprecated before 0.12, but did not have an official warning
 
736
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
 
737
def RevisionTree(*args, **kwargs):
 
738
    """RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
 
739
 
 
740
    Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
 
741
    bzr 0.12.
 
742
    """
 
743
    from bzrlib.revisiontree import RevisionTree as _RevisionTree
 
744
    return _RevisionTree(*args, **kwargs)
 
745
 
 
746