← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-04-09 20:23:07 UTC
  • mfrom: (4265.1.4 bbc-merge)
  • Revision ID: pqm@pqm.ubuntu.com-20090409202307-n0depb16qepoe21o
(jam) Change _fetch_uses_deltas = False for CHK repos until we can
        write a better fix.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tree.py
1
 
# Copyright (C) 2005 Canonical Ltd
 
1
# Copyright (C) 2005, 2009 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
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
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tree classes, representing directory at point in time.
18
18
"""
23
23
 
24
24
import bzrlib
25
25
from bzrlib import (
 
26
    conflicts as _mod_conflicts,
 
27
    debug,
26
28
    delta,
 
29
    filters,
27
30
    osutils,
 
31
    revision as _mod_revision,
 
32
    rules,
28
33
    symbol_versioning,
29
34
    )
30
35
from bzrlib.decorators import needs_read_lock
31
 
from bzrlib.errors import BzrError, BzrCheckError
 
36
from bzrlib.errors import BzrError, BzrCheckError, NoSuchId
32
37
from bzrlib import errors
33
38
from bzrlib.inventory import Inventory, InventoryFile
34
39
from bzrlib.inter import InterObject
35
40
from bzrlib.osutils import fingerprint_file
36
41
import bzrlib.revision
 
42
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
37
43
from bzrlib.trace import mutter, note
38
44
 
39
45
 
41
47
    """Abstract file tree.
42
48
 
43
49
    There are several subclasses:
44
 
    
 
50
 
45
51
    * `WorkingTree` exists as files on disk editable by the user.
46
52
 
47
53
    * `RevisionTree` is a tree as recorded at some point in the past.
56
62
    Trees can be compared, etc, regardless of whether they are working
57
63
    trees or versioned trees.
58
64
    """
59
 
    
 
65
 
60
66
    def changes_from(self, other, want_unchanged=False, specific_files=None,
61
67
        extra_trees=None, require_versioned=False, include_root=False,
62
68
        want_unversioned=False):
76
82
            a PathsNotVersionedError will be thrown.
77
83
        :param want_unversioned: Scan for unversioned paths.
78
84
 
79
 
        The comparison will be performed by an InterTree object looked up on 
 
85
        The comparison will be performed by an InterTree object looked up on
80
86
        self and other.
81
87
        """
82
88
        # Martin observes that Tree.changes_from returns a TreeDelta and this
91
97
            want_unversioned=want_unversioned,
92
98
            )
93
99
 
94
 
    def _iter_changes(self, from_tree, include_unchanged=False,
 
100
    def iter_changes(self, from_tree, include_unchanged=False,
95
101
                     specific_files=None, pb=None, extra_trees=None,
96
102
                     require_versioned=True, want_unversioned=False):
97
103
        intertree = InterTree.get(from_tree, self)
98
 
        return intertree._iter_changes(include_unchanged, specific_files, pb,
 
104
        return intertree.iter_changes(include_unchanged, specific_files, pb,
99
105
            extra_trees, require_versioned, want_unversioned=want_unversioned)
100
 
    
 
106
 
101
107
    def conflicts(self):
102
108
        """Get a list of the conflicts in the tree.
103
109
 
104
110
        Each conflict is an instance of bzrlib.conflicts.Conflict.
105
111
        """
106
 
        return []
 
112
        return _mod_conflicts.ConflictList()
107
113
 
108
114
    def extras(self):
109
115
        """For trees that can have unversioned files, return all such paths."""
110
116
        return []
111
117
 
112
118
    def get_parent_ids(self):
113
 
        """Get the parent ids for this tree. 
 
119
        """Get the parent ids for this tree.
114
120
 
115
121
        :return: a list of parent ids. [] is returned to indicate
116
122
        a tree with no parents.
117
123
        :raises: BzrError if the parents are not known.
118
124
        """
119
125
        raise NotImplementedError(self.get_parent_ids)
120
 
    
 
126
 
121
127
    def has_filename(self, filename):
122
128
        """True if the tree has given filename."""
123
 
        raise NotImplementedError()
 
129
        raise NotImplementedError(self.has_filename)
124
130
 
125
131
    def has_id(self, file_id):
126
 
        file_id = osutils.safe_file_id(file_id)
127
132
        return self.inventory.has_id(file_id)
128
133
 
129
 
    __contains__ = has_id
 
134
    def __contains__(self, file_id):
 
135
        return self.has_id(file_id)
130
136
 
131
137
    def has_or_had_id(self, file_id):
132
 
        file_id = osutils.safe_file_id(file_id)
133
138
        if file_id == self.inventory.root.file_id:
134
139
            return True
135
140
        return self.inventory.has_id(file_id)
145
150
    def __iter__(self):
146
151
        return iter(self.inventory)
147
152
 
 
153
    def all_file_ids(self):
 
154
        """Iterate through all file ids, including ids for missing files."""
 
155
        return set(self.inventory)
 
156
 
148
157
    def id2path(self, file_id):
149
158
        """Return the path for a file id.
150
159
 
151
160
        :raises NoSuchId:
152
161
        """
153
 
        file_id = osutils.safe_file_id(file_id)
154
162
        return self.inventory.id2path(file_id)
155
163
 
156
164
    def is_control_filename(self, filename):
157
165
        """True if filename is the name of a control file in this tree.
158
 
        
 
166
 
159
167
        :param filename: A filename within the tree. This is a relative path
160
168
        from the root of this tree.
161
169
 
169
177
    def iter_entries_by_dir(self, specific_file_ids=None):
170
178
        """Walk the tree in 'by_dir' order.
171
179
 
172
 
        This will yield each entry in the tree as a (path, entry) tuple. The
173
 
        order that they are yielded is: the contents of a directory are 
174
 
        preceeded by the parent of a directory, and all the contents of a 
175
 
        directory are grouped together.
 
180
        This will yield each entry in the tree as a (path, entry) tuple.
 
181
        The order that they are yielded is:
 
182
 
 
183
        Directories are walked in a depth-first lexicographical order,
 
184
        however, whenever a directory is reached, all of its direct child
 
185
        nodes are yielded in  lexicographical order before yielding the
 
186
        grandchildren.
 
187
 
 
188
        For example, in the tree::
 
189
 
 
190
           a/
 
191
             b/
 
192
               c
 
193
             d/
 
194
               e
 
195
           f/
 
196
             g
 
197
 
 
198
        The yield order (ignoring root) would be::
 
199
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
176
200
        """
177
201
        return self.inventory.iter_entries_by_dir(
178
202
            specific_file_ids=specific_file_ids)
186
210
        raise NotImplementedError("Tree subclass %s must implement kind"
187
211
            % self.__class__.__name__)
188
212
 
 
213
    def stored_kind(self, file_id):
 
214
        """File kind stored for this file_id.
 
215
 
 
216
        May not match kind on disk for working trees.  Always available
 
217
        for versioned files, even when the file itself is missing.
 
218
        """
 
219
        return self.kind(file_id)
 
220
 
 
221
    def path_content_summary(self, path):
 
222
        """Get a summary of the information about path.
 
223
 
 
224
        :param path: A relative path within the tree.
 
225
        :return: A tuple containing kind, size, exec, sha1-or-link.
 
226
            Kind is always present (see tree.kind()).
 
227
            size is present if kind is file, None otherwise.
 
228
            exec is None unless kind is file and the platform supports the 'x'
 
229
                bit.
 
230
            sha1-or-link is the link target if kind is symlink, or the sha1 if
 
231
                it can be obtained without reading the file.
 
232
        """
 
233
        raise NotImplementedError(self.path_content_summary)
 
234
 
189
235
    def get_reference_revision(self, file_id, path=None):
190
236
        raise NotImplementedError("Tree subclass %s must implement "
191
237
                                  "get_reference_revision"
207
253
 
208
254
    def _get_inventory(self):
209
255
        return self._inventory
210
 
    
211
 
    def get_file(self, file_id):
212
 
        """Return a file object for the file file_id in the tree."""
 
256
 
 
257
    def get_file(self, file_id, path=None):
 
258
        """Return a file object for the file file_id in the tree.
 
259
 
 
260
        If both file_id and path are defined, it is implementation defined as
 
261
        to which one is used.
 
262
        """
213
263
        raise NotImplementedError(self.get_file)
214
264
 
 
265
    def get_file_text(self, file_id, path=None):
 
266
        """Return the byte content of a file.
 
267
 
 
268
        :param file_id: The file_id of the file.
 
269
        :param path: The path of the file.
 
270
        If both file_id and path are supplied, an implementation may use
 
271
        either one.
 
272
        """
 
273
        my_file = self.get_file(file_id, path)
 
274
        try:
 
275
            return my_file.read()
 
276
        finally:
 
277
            my_file.close()
 
278
 
 
279
    def get_file_lines(self, file_id, path=None):
 
280
        """Return the content of a file, as lines.
 
281
 
 
282
        :param file_id: The file_id of the file.
 
283
        :param path: The path of the file.
 
284
        If both file_id and path are supplied, an implementation may use
 
285
        either one.
 
286
        """
 
287
        return osutils.split_lines(self.get_file_text(file_id, path))
 
288
 
215
289
    def get_file_mtime(self, file_id, path=None):
216
290
        """Return the modification time for a file.
217
291
 
221
295
        """
222
296
        raise NotImplementedError(self.get_file_mtime)
223
297
 
 
298
    def get_file_size(self, file_id):
 
299
        """Return the size of a file in bytes.
 
300
 
 
301
        This applies only to regular files.  If invoked on directories or
 
302
        symlinks, it will return None.
 
303
        :param file_id: The file-id of the file
 
304
        """
 
305
        raise NotImplementedError(self.get_file_size)
 
306
 
224
307
    def get_file_by_path(self, path):
225
 
        return self.get_file(self._inventory.path2id(path))
 
308
        return self.get_file(self._inventory.path2id(path), path)
 
309
 
 
310
    def iter_files_bytes(self, desired_files):
 
311
        """Iterate through file contents.
 
312
 
 
313
        Files will not necessarily be returned in the order they occur in
 
314
        desired_files.  No specific order is guaranteed.
 
315
 
 
316
        Yields pairs of identifier, bytes_iterator.  identifier is an opaque
 
317
        value supplied by the caller as part of desired_files.  It should
 
318
        uniquely identify the file version in the caller's context.  (Examples:
 
319
        an index number or a TreeTransform trans_id.)
 
320
 
 
321
        bytes_iterator is an iterable of bytestrings for the file.  The
 
322
        kind of iterable and length of the bytestrings are unspecified, but for
 
323
        this implementation, it is a tuple containing a single bytestring with
 
324
        the complete text of the file.
 
325
 
 
326
        :param desired_files: a list of (file_id, identifier) pairs
 
327
        """
 
328
        for file_id, identifier in desired_files:
 
329
            # We wrap the string in a tuple so that we can return an iterable
 
330
            # of bytestrings.  (Technically, a bytestring is also an iterable
 
331
            # of bytestrings, but iterating through each character is not
 
332
            # performant.)
 
333
            cur_file = (self.get_file_text(file_id),)
 
334
            yield identifier, cur_file
226
335
 
227
336
    def get_symlink_target(self, file_id):
228
337
        """Get the target for a given file_id.
234
343
        """
235
344
        raise NotImplementedError(self.get_symlink_target)
236
345
 
237
 
    def annotate_iter(self, file_id):
238
 
        """Return an iterator of revision_id, line tuples
 
346
    def get_canonical_inventory_paths(self, paths):
 
347
        """Like get_canonical_inventory_path() but works on multiple items.
 
348
 
 
349
        :param paths: A sequence of paths relative to the root of the tree.
 
350
        :return: A list of paths, with each item the corresponding input path
 
351
        adjusted to account for existing elements that match case
 
352
        insensitively.
 
353
        """
 
354
        return list(self._yield_canonical_inventory_paths(paths))
 
355
 
 
356
    def get_canonical_inventory_path(self, path):
 
357
        """Returns the first inventory item that case-insensitively matches path.
 
358
 
 
359
        If a path matches exactly, it is returned. If no path matches exactly
 
360
        but more than one path matches case-insensitively, it is implementation
 
361
        defined which is returned.
 
362
 
 
363
        If no path matches case-insensitively, the input path is returned, but
 
364
        with as many path entries that do exist changed to their canonical
 
365
        form.
 
366
 
 
367
        If you need to resolve many names from the same tree, you should
 
368
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
369
 
 
370
        :param path: A paths relative to the root of the tree.
 
371
        :return: The input path adjusted to account for existing elements
 
372
        that match case insensitively.
 
373
        """
 
374
        return self._yield_canonical_inventory_paths([path]).next()
 
375
 
 
376
    def _yield_canonical_inventory_paths(self, paths):
 
377
        for path in paths:
 
378
            # First, if the path as specified exists exactly, just use it.
 
379
            if self.path2id(path) is not None:
 
380
                yield path
 
381
                continue
 
382
            # go walkin...
 
383
            cur_id = self.get_root_id()
 
384
            cur_path = ''
 
385
            bit_iter = iter(path.split("/"))
 
386
            for elt in bit_iter:
 
387
                lelt = elt.lower()
 
388
                for child in self.iter_children(cur_id):
 
389
                    try:
 
390
                        child_base = os.path.basename(self.id2path(child))
 
391
                        if child_base.lower() == lelt:
 
392
                            cur_id = child
 
393
                            cur_path = osutils.pathjoin(cur_path, child_base)
 
394
                            break
 
395
                    except NoSuchId:
 
396
                        # before a change is committed we can see this error...
 
397
                        continue
 
398
                else:
 
399
                    # got to the end of this directory and no entries matched.
 
400
                    # Return what matched so far, plus the rest as specified.
 
401
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
402
                    break
 
403
            yield cur_path
 
404
        # all done.
 
405
 
 
406
    def get_root_id(self):
 
407
        """Return the file_id for the root of this tree."""
 
408
        raise NotImplementedError(self.get_root_id)
 
409
 
 
410
    def annotate_iter(self, file_id,
 
411
                      default_revision=_mod_revision.CURRENT_REVISION):
 
412
        """Return an iterator of revision_id, line tuples.
239
413
 
240
414
        For working trees (and mutable trees in general), the special
241
415
        revision_id 'current:' will be used for lines that are new in this
242
416
        tree, e.g. uncommitted changes.
243
417
        :param file_id: The file to produce an annotated version from
 
418
        :param default_revision: For lines that don't match a basis, mark them
 
419
            with this revision id. Not all implementations will make use of
 
420
            this value.
244
421
        """
245
422
        raise NotImplementedError(self.annotate_iter)
246
423
 
 
424
    def _get_plan_merge_data(self, file_id, other, base):
 
425
        from bzrlib import merge, versionedfile
 
426
        vf = versionedfile._PlanMergeVersionedFile(file_id)
 
427
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
 
428
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
 
429
        if base is None:
 
430
            last_revision_base = None
 
431
        else:
 
432
            last_revision_base = base._get_file_revision(file_id, vf, 'base:')
 
433
        return vf, last_revision_a, last_revision_b, last_revision_base
 
434
 
 
435
    def plan_file_merge(self, file_id, other, base=None):
 
436
        """Generate a merge plan based on annotations.
 
437
 
 
438
        If the file contains uncommitted changes in this tree, they will be
 
439
        attributed to the 'current:' pseudo-revision.  If the file contains
 
440
        uncommitted changes in the other tree, they will be assigned to the
 
441
        'other:' pseudo-revision.
 
442
        """
 
443
        data = self._get_plan_merge_data(file_id, other, base)
 
444
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
445
        return vf.plan_merge(last_revision_a, last_revision_b,
 
446
                             last_revision_base)
 
447
 
 
448
    def plan_file_lca_merge(self, file_id, other, base=None):
 
449
        """Generate a merge plan based lca-newness.
 
450
 
 
451
        If the file contains uncommitted changes in this tree, they will be
 
452
        attributed to the 'current:' pseudo-revision.  If the file contains
 
453
        uncommitted changes in the other tree, they will be assigned to the
 
454
        'other:' pseudo-revision.
 
455
        """
 
456
        data = self._get_plan_merge_data(file_id, other, base)
 
457
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
458
        return vf.plan_lca_merge(last_revision_a, last_revision_b,
 
459
                                 last_revision_base)
 
460
 
 
461
    def _iter_parent_trees(self):
 
462
        """Iterate through parent trees, defaulting to Tree.revision_tree."""
 
463
        for revision_id in self.get_parent_ids():
 
464
            try:
 
465
                yield self.revision_tree(revision_id)
 
466
            except errors.NoSuchRevisionInTree:
 
467
                yield self.repository.revision_tree(revision_id)
 
468
 
 
469
    @staticmethod
 
470
    def _file_revision(revision_tree, file_id):
 
471
        """Determine the revision associated with a file in a given tree."""
 
472
        revision_tree.lock_read()
 
473
        try:
 
474
            return revision_tree.inventory[file_id].revision
 
475
        finally:
 
476
            revision_tree.unlock()
 
477
 
 
478
    def _get_file_revision(self, file_id, vf, tree_revision):
 
479
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
 
480
 
 
481
        if getattr(self, '_repository', None) is None:
 
482
            last_revision = tree_revision
 
483
            parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
 
484
                self._iter_parent_trees()]
 
485
            vf.add_lines((file_id, last_revision), parent_keys,
 
486
                         self.get_file(file_id).readlines())
 
487
            repo = self.branch.repository
 
488
            base_vf = repo.texts
 
489
        else:
 
490
            last_revision = self._file_revision(self, file_id)
 
491
            base_vf = self._repository.texts
 
492
        if base_vf not in vf.fallback_versionedfiles:
 
493
            vf.fallback_versionedfiles.append(base_vf)
 
494
        return last_revision
 
495
 
247
496
    inventory = property(_get_inventory,
248
497
                         doc="Inventory of this Tree")
249
498
 
250
499
    def _check_retrieved(self, ie, f):
251
500
        if not __debug__:
252
 
            return  
 
501
            return
253
502
        fp = fingerprint_file(f)
254
503
        f.seek(0)
255
 
        
 
504
 
256
505
        if ie.text_size is not None:
257
506
            if ie.text_size != fp['size']:
258
507
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
273
522
 
274
523
    def paths2ids(self, paths, trees=[], require_versioned=True):
275
524
        """Return all the ids that can be reached by walking from paths.
276
 
        
277
 
        Each path is looked up in each this tree and any extras provided in
 
525
 
 
526
        Each path is looked up in this tree and any extras provided in
278
527
        trees, and this is repeated recursively: the children in an extra tree
279
528
        of a directory that has been renamed under a provided path in this tree
280
 
        are all returned, even if none exist until a provided path in this
 
529
        are all returned, even if none exist under a provided path in this
281
530
        tree, and vice versa.
282
531
 
283
532
        :param paths: An iterable of paths to start converting to ids from.
290
539
        """
291
540
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
292
541
 
293
 
    def print_file(self, file_id):
294
 
        """Print file with id `file_id` to stdout."""
295
 
        file_id = osutils.safe_file_id(file_id)
296
 
        import sys
297
 
        sys.stdout.write(self.get_file_text(file_id))
 
542
    def iter_children(self, file_id):
 
543
        entry = self.iter_entries_by_dir([file_id]).next()[1]
 
544
        for child in getattr(entry, 'children', {}).itervalues():
 
545
            yield child.file_id
298
546
 
299
547
    def lock_read(self):
300
548
        pass
304
552
 
305
553
        The intention of this method is to allow access to possibly cached
306
554
        tree data. Implementors of this method should raise NoSuchRevision if
307
 
        the tree is not locally available, even if they could obtain the 
308
 
        tree via a repository or some other means. Callers are responsible 
 
555
        the tree is not locally available, even if they could obtain the
 
556
        tree via a repository or some other means. Callers are responsible
309
557
        for finding the ultimate source for a revision tree.
310
558
 
311
559
        :param revision_id: The revision_id of the requested tree.
316
564
 
317
565
    def unknowns(self):
318
566
        """What files are present in this tree and unknown.
319
 
        
 
567
 
320
568
        :return: an iterator over the unknown files.
321
569
        """
322
570
        return iter([])
330
578
        :return: set of paths.
331
579
        """
332
580
        # NB: we specifically *don't* call self.has_filename, because for
333
 
        # WorkingTrees that can indicate files that exist on disk but that 
 
581
        # WorkingTrees that can indicate files that exist on disk but that
334
582
        # are not versioned.
335
583
        pred = self.inventory.has_filename
336
584
        return set((p for p in paths if not pred(p)))
341
589
        This yields all the data about the contents of a directory at a time.
342
590
        After each directory has been yielded, if the caller has mutated the
343
591
        list to exclude some directories, they are then not descended into.
344
 
        
 
592
 
345
593
        The data yielded is of the form:
346
594
        ((directory-relpath, directory-path-from-root, directory-fileid),
347
 
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id, 
 
595
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id,
348
596
          versioned_kind), ...]),
349
597
         - directory-relpath is the containing dirs relpath from prefix
350
598
         - directory-path-from-root is the containing dirs path from /
356
604
           versioned_kind.
357
605
         - lstat is the stat data *if* the file was statted.
358
606
         - path_from_tree_root is the path from the root of the tree.
359
 
         - file_id is the file_id is the entry is versioned.
360
 
         - versioned_kind is the kind of the file as last recorded in the 
 
607
         - file_id is the file_id if the entry is versioned.
 
608
         - versioned_kind is the kind of the file as last recorded in the
361
609
           versioning system. If 'unknown' the file is not versioned.
362
610
        One of 'kind' and 'versioned_kind' must not be 'unknown'.
363
611
 
368
616
        """
369
617
        raise NotImplementedError(self.walkdirs)
370
618
 
371
 
 
372
 
class EmptyTree(Tree):
373
 
 
374
 
    def __init__(self):
375
 
        self._inventory = Inventory(root_id=None)
376
 
        symbol_versioning.warn('EmptyTree is deprecated as of bzr 0.9 please'
377
 
                               ' use repository.revision_tree instead.',
378
 
                               DeprecationWarning, stacklevel=2)
379
 
 
380
 
    def get_parent_ids(self):
381
 
        return []
382
 
 
383
 
    def get_symlink_target(self, file_id):
384
 
        return None
385
 
 
386
 
    def has_filename(self, filename):
 
619
    def supports_content_filtering(self):
387
620
        return False
388
621
 
389
 
    def kind(self, file_id):
390
 
        file_id = osutils.safe_file_id(file_id)
391
 
        assert self._inventory[file_id].kind == "directory"
392
 
        return "directory"
393
 
 
394
 
    def list_files(self, include_root=False):
395
 
        return iter([])
396
 
    
397
 
    def __contains__(self, file_id):
398
 
        file_id = osutils.safe_file_id(file_id)
399
 
        return (file_id in self._inventory)
400
 
 
401
 
    def get_file_sha1(self, file_id, path=None, stat_value=None):
402
 
        return None
 
622
    def _content_filter_stack(self, path=None, file_id=None):
 
623
        """The stack of content filters for a path if filtering is supported.
 
624
 
 
625
        Readers will be applied in first-to-last order.
 
626
        Writers will be applied in last-to-first order.
 
627
        Either the path or the file-id needs to be provided.
 
628
 
 
629
        :param path: path relative to the root of the tree
 
630
            or None if unknown
 
631
        :param file_id: file_id or None if unknown
 
632
        :return: the list of filters - [] if there are none
 
633
        """
 
634
        filter_pref_names = filters._get_registered_names()
 
635
        if len(filter_pref_names) == 0:
 
636
            return []
 
637
        if path is None:
 
638
            path = self.id2path(file_id)
 
639
        prefs = self.iter_search_rules([path], filter_pref_names).next()
 
640
        stk = filters._get_filter_stack_for(prefs)
 
641
        if 'filters' in debug.debug_flags:
 
642
            note("*** %s content-filter: %s => %r" % (path,prefs,stk))
 
643
        return stk
 
644
 
 
645
    def _content_filter_stack_provider(self):
 
646
        """A function that returns a stack of ContentFilters.
 
647
 
 
648
        The function takes a path (relative to the top of the tree) and a
 
649
        file-id as parameters.
 
650
 
 
651
        :return: None if content filtering is not supported by this tree.
 
652
        """
 
653
        if self.supports_content_filtering():
 
654
            return lambda path, file_id: \
 
655
                    self._content_filter_stack(path, file_id)
 
656
        else:
 
657
            return None
 
658
 
 
659
    def iter_search_rules(self, path_names, pref_names=None,
 
660
        _default_searcher=rules._per_user_searcher):
 
661
        """Find the preferences for filenames in a tree.
 
662
 
 
663
        :param path_names: an iterable of paths to find attributes for.
 
664
          Paths are given relative to the root of the tree.
 
665
        :param pref_names: the list of preferences to lookup - None for all
 
666
        :param _default_searcher: private parameter to assist testing - don't use
 
667
        :return: an iterator of tuple sequences, one per path-name.
 
668
          See _RulesSearcher.get_items for details on the tuple sequence.
 
669
        """
 
670
        searcher = self._get_rules_searcher(_default_searcher)
 
671
        if searcher is not None:
 
672
            if pref_names is not None:
 
673
                for path in path_names:
 
674
                    yield searcher.get_selected_items(path, pref_names)
 
675
            else:
 
676
                for path in path_names:
 
677
                    yield searcher.get_items(path)
 
678
 
 
679
    @needs_read_lock
 
680
    def _get_rules_searcher(self, default_searcher):
 
681
        """Get the RulesSearcher for this tree given the default one."""
 
682
        searcher = default_searcher
 
683
        return searcher
403
684
 
404
685
 
405
686
######################################################################
438
719
        # what happened to the file that used to have
439
720
        # this name.  There are two possibilities: either it was
440
721
        # deleted entirely, or renamed.
441
 
        assert old_id
442
722
        if new_inv.has_id(old_id):
443
723
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
444
724
        else:
455
735
 
456
736
    return 'wtf?'
457
737
 
458
 
    
459
738
 
 
739
@deprecated_function(deprecated_in((1, 9, 0)))
460
740
def find_renames(old_inv, new_inv):
461
741
    for file_id in old_inv:
462
742
        if file_id not in new_inv:
465
745
        new_name = new_inv.id2path(file_id)
466
746
        if old_name != new_name:
467
747
            yield (old_name, new_name)
468
 
            
 
748
 
469
749
 
470
750
def find_ids_across_trees(filenames, trees, require_versioned=True):
471
751
    """Find the ids corresponding to specified filenames.
472
 
    
 
752
 
473
753
    All matches in all trees will be used, and all children of matched
474
754
    directories will be used.
475
755
 
489
769
 
490
770
def _find_ids_across_trees(filenames, trees, require_versioned):
491
771
    """Find the ids corresponding to specified filenames.
492
 
    
 
772
 
493
773
    All matches in all trees will be used, but subdirectories are not scanned.
494
774
 
495
775
    :param filenames: The filenames to find file_ids for
496
776
    :param trees: The trees to find file_ids within
497
777
    :param require_versioned: if true, all specified filenames must occur in
498
778
        at least one tree.
499
 
    :return: a set of (path, file ids) for the specified filenames
 
779
    :return: a set of file ids for the specified filenames
500
780
    """
501
781
    not_versioned = []
502
782
    interesting_ids = set()
515
795
 
516
796
 
517
797
def _find_children_across_trees(specified_ids, trees):
518
 
    """Return a set including specified ids and their children
519
 
    
 
798
    """Return a set including specified ids and their children.
 
799
 
520
800
    All matches in all trees will be used.
521
801
 
522
802
    :param trees: The trees to find file_ids within
523
 
    :return: a set containing all specified ids and their children 
 
803
    :return: a set containing all specified ids and their children
524
804
    """
525
805
    interesting_ids = set(specified_ids)
526
806
    pending = interesting_ids
532
812
            for tree in trees:
533
813
                if not tree.has_id(file_id):
534
814
                    continue
535
 
                entry = tree.inventory[file_id]
536
 
                for child in getattr(entry, 'children', {}).itervalues():
537
 
                    if child.file_id not in interesting_ids:
538
 
                        new_pending.add(child.file_id)
 
815
                for child_id in tree.iter_children(file_id):
 
816
                    if child_id not in interesting_ids:
 
817
                        new_pending.add(child_id)
539
818
        interesting_ids.update(new_pending)
540
819
        pending = new_pending
541
820
    return interesting_ids
547
826
    Its instances have methods like 'compare' and contain references to the
548
827
    source and target trees these operations are to be carried out on.
549
828
 
550
 
    clients of bzrlib should not need to use InterTree directly, rather they
 
829
    Clients of bzrlib should not need to use InterTree directly, rather they
551
830
    should use the convenience methods on Tree such as 'Tree.compare()' which
552
831
    will pass through to InterTree as appropriate.
553
832
    """
593
872
            return result
594
873
        return delta._compare_trees(self.source, self.target, want_unchanged,
595
874
            specific_files, include_root, extra_trees=extra_trees,
 
875
            require_versioned=require_versioned,
596
876
            want_unversioned=want_unversioned)
597
877
 
598
 
    def _iter_changes(self, include_unchanged=False,
 
878
    def iter_changes(self, include_unchanged=False,
599
879
                      specific_files=None, pb=None, extra_trees=[],
600
880
                      require_versioned=True, want_unversioned=False):
601
881
        """Generate an iterator of changes between trees.
625
905
            output. An unversioned file is defined as one with (False, False)
626
906
            for the versioned pair.
627
907
        """
628
 
        result = []
629
908
        lookup_trees = [self.source]
630
909
        if extra_trees:
631
910
             lookup_trees.extend(extra_trees)
632
 
        specific_file_ids = self.target.paths2ids(specific_files,
633
 
            lookup_trees, require_versioned=require_versioned)
 
911
        if specific_files == []:
 
912
            specific_file_ids = []
 
913
        else:
 
914
            specific_file_ids = self.target.paths2ids(specific_files,
 
915
                lookup_trees, require_versioned=require_versioned)
634
916
        if want_unversioned:
635
 
            all_unversioned = sorted([(p.split('/'), p) for p in self.target.extras()
636
 
                if not specific_files or
 
917
            all_unversioned = sorted([(p.split('/'), p) for p in
 
918
                                     self.target.extras()
 
919
                if specific_files is None or
637
920
                    osutils.is_inside_any(specific_files, p)])
638
921
            all_unversioned = deque(all_unversioned)
639
922
        else:
640
923
            all_unversioned = deque()
641
924
        to_paths = {}
642
 
        from_entries_by_dir = list(self.source.inventory.iter_entries_by_dir(
 
925
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
643
926
            specific_file_ids=specific_file_ids))
644
927
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
645
 
        to_entries_by_dir = list(self.target.inventory.iter_entries_by_dir(
 
928
        to_entries_by_dir = list(self.target.iter_entries_by_dir(
646
929
            specific_file_ids=specific_file_ids))
647
930
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
648
931
        entry_count = 0
649
 
        # the unversioned path lookup only occurs on real trees - where there 
 
932
        # the unversioned path lookup only occurs on real trees - where there
650
933
        # can be extras. So the fake_entry is solely used to look up
651
934
        # executable it values when execute is not supported.
652
935
        fake_entry = InventoryFile('unused', 'unused', 'unused')
686
969
            if kind[0] != kind[1]:
687
970
                changed_content = True
688
971
            elif from_kind == 'file':
689
 
                from_size = self.source._file_size(from_entry, from_stat)
690
 
                to_size = self.target._file_size(to_entry, to_stat)
691
 
                if from_size != to_size:
692
 
                    changed_content = True
693
 
                elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
 
972
                if (self.source.get_file_sha1(file_id, from_path, from_stat) !=
694
973
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
695
974
                    changed_content = True
696
975
            elif from_kind == 'symlink':
697
976
                if (self.source.get_symlink_target(file_id) !=
698
977
                    self.target.get_symlink_target(file_id)):
699
978
                    changed_content = True
 
979
                # XXX: Yes, the indentation below is wrong. But fixing it broke
 
980
                # test_merge.TestMergerEntriesLCAOnDisk.
 
981
                # test_nested_tree_subtree_renamed_and_modified. We'll wait for
 
982
                # the fix from bzr.dev -- vila 2009026
700
983
                elif from_kind == 'tree-reference':
701
984
                    if (self.source.get_reference_revision(file_id, from_path)
702
985
                        != self.target.get_reference_revision(file_id, to_path)):
703
 
                        changed_content = True 
 
986
                        changed_content = True
704
987
            parent = (from_parent, to_entry.parent_id)
705
988
            name = (from_name, to_entry.name)
706
989
            executable = (from_executable, to_executable)
707
990
            if pb is not None:
708
991
                pb.update('comparing files', entry_count, num_entries)
709
992
            if (changed_content is not False or versioned[0] != versioned[1]
710
 
                or parent[0] != parent[1] or name[0] != name[1] or 
 
993
                or parent[0] != parent[1] or name[0] != name[1] or
711
994
                executable[0] != executable[1] or include_unchanged):
712
995
                yield (file_id, (from_path, to_path), changed_content,
713
996
                    versioned, parent, name, kind, executable)
740
1023
            if file_id in to_paths:
741
1024
                # already returned
742
1025
                continue
743
 
            if not file_id in self.target.inventory:
 
1026
            if not file_id in self.target.all_file_ids():
744
1027
                # common case - paths we have not emitted are not present in
745
1028
                # target.
746
1029
                to_path = None
756
1039
                self.source._comparison_data(from_entry, path)
757
1040
            kind = (from_kind, None)
758
1041
            executable = (from_executable, None)
759
 
            changed_content = True
 
1042
            changed_content = from_kind is not None
760
1043
            # the parent's path is necessarily known at this point.
761
1044
            yield(file_id, (path, to_path), changed_content, versioned, parent,
762
1045
                  name, kind, executable)
763
1046
 
764
1047
 
765
 
# This was deprecated before 0.12, but did not have an official warning
766
 
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
767
 
def RevisionTree(*args, **kwargs):
768
 
    """RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
769
 
 
770
 
    Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
771
 
    bzr 0.12.
772
 
    """
773
 
    from bzrlib.revisiontree import RevisionTree as _RevisionTree
774
 
    return _RevisionTree(*args, **kwargs)
775
 
 
776
 
 
 
1048
class MultiWalker(object):
 
1049
    """Walk multiple trees simultaneously, getting combined results."""
 
1050
 
 
1051
    # Note: This could be written to not assume you can do out-of-order
 
1052
    #       lookups. Instead any nodes that don't match in all trees could be
 
1053
    #       marked as 'deferred', and then returned in the final cleanup loop.
 
1054
    #       For now, I think it is "nicer" to return things as close to the
 
1055
    #       "master_tree" order as we can.
 
1056
 
 
1057
    def __init__(self, master_tree, other_trees):
 
1058
        """Create a new MultiWalker.
 
1059
 
 
1060
        All trees being walked must implement "iter_entries_by_dir()", such
 
1061
        that they yield (path, object) tuples, where that object will have a
 
1062
        '.file_id' member, that can be used to check equality.
 
1063
 
 
1064
        :param master_tree: All trees will be 'slaved' to the master_tree such
 
1065
            that nodes in master_tree will be used as 'first-pass' sync points.
 
1066
            Any nodes that aren't in master_tree will be merged in a second
 
1067
            pass.
 
1068
        :param other_trees: A list of other trees to walk simultaneously.
 
1069
        """
 
1070
        self._master_tree = master_tree
 
1071
        self._other_trees = other_trees
 
1072
 
 
1073
        # Keep track of any nodes that were properly processed just out of
 
1074
        # order, that way we don't return them at the end, we don't have to
 
1075
        # track *all* processed file_ids, just the out-of-order ones
 
1076
        self._out_of_order_processed = set()
 
1077
 
 
1078
    @staticmethod
 
1079
    def _step_one(iterator):
 
1080
        """Step an iter_entries_by_dir iterator.
 
1081
 
 
1082
        :return: (has_more, path, ie)
 
1083
            If has_more is False, path and ie will be None.
 
1084
        """
 
1085
        try:
 
1086
            path, ie = iterator.next()
 
1087
        except StopIteration:
 
1088
            return False, None, None
 
1089
        else:
 
1090
            return True, path, ie
 
1091
 
 
1092
    @staticmethod
 
1093
    def _cmp_path_by_dirblock(path1, path2):
 
1094
        """Compare two paths based on what directory they are in.
 
1095
 
 
1096
        This generates a sort order, such that all children of a directory are
 
1097
        sorted together, and grandchildren are in the same order as the
 
1098
        children appear. But all grandchildren come after all children.
 
1099
 
 
1100
        :param path1: first path
 
1101
        :param path2: the second path
 
1102
        :return: negative number if ``path1`` comes first,
 
1103
            0 if paths are equal
 
1104
            and a positive number if ``path2`` sorts first
 
1105
        """
 
1106
        # Shortcut this special case
 
1107
        if path1 == path2:
 
1108
            return 0
 
1109
        # This is stolen from _dirstate_helpers_py.py, only switching it to
 
1110
        # Unicode objects. Consider using encode_utf8() and then using the
 
1111
        # optimized versions, or maybe writing optimized unicode versions.
 
1112
        if not isinstance(path1, unicode):
 
1113
            raise TypeError("'path1' must be a unicode string, not %s: %r"
 
1114
                            % (type(path1), path1))
 
1115
        if not isinstance(path2, unicode):
 
1116
            raise TypeError("'path2' must be a unicode string, not %s: %r"
 
1117
                            % (type(path2), path2))
 
1118
        return cmp(MultiWalker._path_to_key(path1),
 
1119
                   MultiWalker._path_to_key(path2))
 
1120
 
 
1121
    @staticmethod
 
1122
    def _path_to_key(path):
 
1123
        dirname, basename = osutils.split(path)
 
1124
        return (dirname.split(u'/'), basename)
 
1125
 
 
1126
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
 
1127
        """Lookup an inventory entry by file_id.
 
1128
 
 
1129
        This is called when an entry is missing in the normal order.
 
1130
        Generally this is because a file was either renamed, or it was
 
1131
        deleted/added. If the entry was found in the inventory and not in
 
1132
        extra_entries, it will be added to self._out_of_order_processed
 
1133
 
 
1134
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
 
1135
            should be filled with entries that were found before they were
 
1136
            used. If file_id is present, it will be removed from the
 
1137
            dictionary.
 
1138
        :param other_tree: The Tree to search, in case we didn't find the entry
 
1139
            yet.
 
1140
        :param file_id: The file_id to look for
 
1141
        :return: (path, ie) if found or (None, None) if not present.
 
1142
        """
 
1143
        if file_id in extra_entries:
 
1144
            return extra_entries.pop(file_id)
 
1145
        # TODO: Is id2path better as the first call, or is
 
1146
        #       inventory[file_id] better as a first check?
 
1147
        try:
 
1148
            cur_path = other_tree.id2path(file_id)
 
1149
        except errors.NoSuchId:
 
1150
            cur_path = None
 
1151
        if cur_path is None:
 
1152
            return (None, None)
 
1153
        else:
 
1154
            self._out_of_order_processed.add(file_id)
 
1155
            cur_ie = other_tree.inventory[file_id]
 
1156
            return (cur_path, cur_ie)
 
1157
 
 
1158
    def iter_all(self):
 
1159
        """Match up the values in the different trees."""
 
1160
        for result in self._walk_master_tree():
 
1161
            yield result
 
1162
        self._finish_others()
 
1163
        for result in self._walk_others():
 
1164
            yield result
 
1165
 
 
1166
    def _walk_master_tree(self):
 
1167
        """First pass, walk all trees in lock-step.
 
1168
 
 
1169
        When we are done, all nodes in the master_tree will have been
 
1170
        processed. _other_walkers, _other_entries, and _others_extra will be
 
1171
        set on 'self' for future processing.
 
1172
        """
 
1173
        # This iterator has the most "inlining" done, because it tends to touch
 
1174
        # every file in the tree, while the others only hit nodes that don't
 
1175
        # match.
 
1176
        master_iterator = self._master_tree.iter_entries_by_dir()
 
1177
 
 
1178
        other_walkers = [other.iter_entries_by_dir()
 
1179
                         for other in self._other_trees]
 
1180
        other_entries = [self._step_one(walker) for walker in other_walkers]
 
1181
        # Track extra nodes in the other trees
 
1182
        others_extra = [{} for i in xrange(len(self._other_trees))]
 
1183
 
 
1184
        master_has_more = True
 
1185
        step_one = self._step_one
 
1186
        lookup_by_file_id = self._lookup_by_file_id
 
1187
        out_of_order_processed = self._out_of_order_processed
 
1188
 
 
1189
        while master_has_more:
 
1190
            (master_has_more, path, master_ie) = step_one(master_iterator)
 
1191
            if not master_has_more:
 
1192
                break
 
1193
 
 
1194
            file_id = master_ie.file_id
 
1195
            other_values = []
 
1196
            other_values_append = other_values.append
 
1197
            next_other_entries = []
 
1198
            next_other_entries_append = next_other_entries.append
 
1199
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
 
1200
                if not other_has_more:
 
1201
                    other_values_append(lookup_by_file_id(
 
1202
                        others_extra[idx], self._other_trees[idx], file_id))
 
1203
                    next_other_entries_append((False, None, None))
 
1204
                elif file_id == other_ie.file_id:
 
1205
                    # This is the critical code path, as most of the entries
 
1206
                    # should match between most trees.
 
1207
                    other_values_append((other_path, other_ie))
 
1208
                    next_other_entries_append(step_one(other_walkers[idx]))
 
1209
                else:
 
1210
                    # This walker did not match, step it until it either
 
1211
                    # matches, or we know we are past the current walker.
 
1212
                    other_walker = other_walkers[idx]
 
1213
                    other_extra = others_extra[idx]
 
1214
                    while (other_has_more and
 
1215
                           self._cmp_path_by_dirblock(other_path, path) < 0):
 
1216
                        other_file_id = other_ie.file_id
 
1217
                        if other_file_id not in out_of_order_processed:
 
1218
                            other_extra[other_file_id] = (other_path, other_ie)
 
1219
                        other_has_more, other_path, other_ie = \
 
1220
                            step_one(other_walker)
 
1221
                    if other_has_more and other_ie.file_id == file_id:
 
1222
                        # We ended up walking to this point, match and step
 
1223
                        # again
 
1224
                        other_values_append((other_path, other_ie))
 
1225
                        other_has_more, other_path, other_ie = \
 
1226
                            step_one(other_walker)
 
1227
                    else:
 
1228
                        # This record isn't in the normal order, see if it
 
1229
                        # exists at all.
 
1230
                        other_values_append(lookup_by_file_id(
 
1231
                            other_extra, self._other_trees[idx], file_id))
 
1232
                    next_other_entries_append((other_has_more, other_path,
 
1233
                                               other_ie))
 
1234
            other_entries = next_other_entries
 
1235
 
 
1236
            # We've matched all the walkers, yield this datapoint
 
1237
            yield path, file_id, master_ie, other_values
 
1238
        self._other_walkers = other_walkers
 
1239
        self._other_entries = other_entries
 
1240
        self._others_extra = others_extra
 
1241
 
 
1242
    def _finish_others(self):
 
1243
        """Finish walking the other iterators, so we get all entries."""
 
1244
        for idx, info in enumerate(self._other_entries):
 
1245
            other_extra = self._others_extra[idx]
 
1246
            (other_has_more, other_path, other_ie) = info
 
1247
            while other_has_more:
 
1248
                other_file_id = other_ie.file_id
 
1249
                if other_file_id not in self._out_of_order_processed:
 
1250
                    other_extra[other_file_id] = (other_path, other_ie)
 
1251
                other_has_more, other_path, other_ie = \
 
1252
                    self._step_one(self._other_walkers[idx])
 
1253
        del self._other_entries
 
1254
 
 
1255
    def _walk_others(self):
 
1256
        """Finish up by walking all the 'deferred' nodes."""
 
1257
        # TODO: One alternative would be to grab all possible unprocessed
 
1258
        #       file_ids, and then sort by path, and then yield them. That
 
1259
        #       might ensure better ordering, in case a caller strictly
 
1260
        #       requires parents before children.
 
1261
        for idx, other_extra in enumerate(self._others_extra):
 
1262
            others = sorted(other_extra.itervalues(),
 
1263
                            key=lambda x: self._path_to_key(x[0]))
 
1264
            for other_path, other_ie in others:
 
1265
                file_id = other_ie.file_id
 
1266
                # We don't need to check out_of_order_processed here, because
 
1267
                # the lookup_by_file_id will be removing anything processed
 
1268
                # from the extras cache
 
1269
                other_extra.pop(file_id)
 
1270
                other_values = [(None, None) for i in xrange(idx)]
 
1271
                other_values.append((other_path, other_ie))
 
1272
                for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
 
1273
                    alt_idx = alt_idx + idx + 1
 
1274
                    alt_extra = self._others_extra[alt_idx]
 
1275
                    alt_tree = self._other_trees[alt_idx]
 
1276
                    other_values.append(self._lookup_by_file_id(
 
1277
                                            alt_extra, alt_tree, file_id))
 
1278
                yield other_path, file_id, None, other_values