← 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: 2010-11-06 16:01:48 UTC
  • mfrom: (5527.1.1 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20101106160148-8maemz21jbrhpzky
(vila) Move NEWS entry into the correct section (Vincent Ladeuil)

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-2010 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
"""
19
19
 
20
20
import os
21
21
from collections import deque
22
 
from cStringIO import StringIO
23
22
 
24
23
import bzrlib
25
24
from bzrlib import (
 
25
    conflicts as _mod_conflicts,
 
26
    debug,
26
27
    delta,
 
28
    filters,
27
29
    osutils,
28
30
    revision as _mod_revision,
29
 
    conflicts as _mod_conflicts,
30
 
    symbol_versioning,
 
31
    rules,
31
32
    )
32
33
from bzrlib.decorators import needs_read_lock
33
 
from bzrlib.errors import BzrError, BzrCheckError
 
34
from bzrlib.errors import BzrError, NoSuchId
34
35
from bzrlib import errors
35
 
from bzrlib.inventory import Inventory, InventoryFile
 
36
from bzrlib.inventory import InventoryFile
36
37
from bzrlib.inter import InterObject
37
38
from bzrlib.osutils import fingerprint_file
38
 
import bzrlib.revision
39
 
from bzrlib.trace import mutter, note
 
39
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
 
40
from bzrlib.trace import note
40
41
 
41
42
 
42
43
class Tree(object):
43
44
    """Abstract file tree.
44
45
 
45
46
    There are several subclasses:
46
 
    
 
47
 
47
48
    * `WorkingTree` exists as files on disk editable by the user.
48
49
 
49
50
    * `RevisionTree` is a tree as recorded at some point in the past.
58
59
    Trees can be compared, etc, regardless of whether they are working
59
60
    trees or versioned trees.
60
61
    """
61
 
    
 
62
 
62
63
    def changes_from(self, other, want_unchanged=False, specific_files=None,
63
64
        extra_trees=None, require_versioned=False, include_root=False,
64
65
        want_unversioned=False):
78
79
            a PathsNotVersionedError will be thrown.
79
80
        :param want_unversioned: Scan for unversioned paths.
80
81
 
81
 
        The comparison will be performed by an InterTree object looked up on 
 
82
        The comparison will be performed by an InterTree object looked up on
82
83
        self and other.
83
84
        """
84
85
        # Martin observes that Tree.changes_from returns a TreeDelta and this
93
94
            want_unversioned=want_unversioned,
94
95
            )
95
96
 
96
 
    def _iter_changes(self, from_tree, include_unchanged=False,
 
97
    def iter_changes(self, from_tree, include_unchanged=False,
97
98
                     specific_files=None, pb=None, extra_trees=None,
98
99
                     require_versioned=True, want_unversioned=False):
 
100
        """See InterTree.iter_changes"""
99
101
        intertree = InterTree.get(from_tree, self)
100
 
        return intertree._iter_changes(include_unchanged, specific_files, pb,
 
102
        return intertree.iter_changes(include_unchanged, specific_files, pb,
101
103
            extra_trees, require_versioned, want_unversioned=want_unversioned)
102
 
    
 
104
 
103
105
    def conflicts(self):
104
106
        """Get a list of the conflicts in the tree.
105
107
 
112
114
        return []
113
115
 
114
116
    def get_parent_ids(self):
115
 
        """Get the parent ids for this tree. 
 
117
        """Get the parent ids for this tree.
116
118
 
117
119
        :return: a list of parent ids. [] is returned to indicate
118
120
        a tree with no parents.
119
121
        :raises: BzrError if the parents are not known.
120
122
        """
121
123
        raise NotImplementedError(self.get_parent_ids)
122
 
    
 
124
 
123
125
    def has_filename(self, filename):
124
126
        """True if the tree has given filename."""
125
127
        raise NotImplementedError(self.has_filename)
127
129
    def has_id(self, file_id):
128
130
        return self.inventory.has_id(file_id)
129
131
 
130
 
    __contains__ = has_id
 
132
    def __contains__(self, file_id):
 
133
        return self.has_id(file_id)
131
134
 
132
135
    def has_or_had_id(self, file_id):
133
 
        if file_id == self.inventory.root.file_id:
134
 
            return True
135
136
        return self.inventory.has_id(file_id)
136
137
 
137
138
    def is_ignored(self, filename):
145
146
    def __iter__(self):
146
147
        return iter(self.inventory)
147
148
 
 
149
    def all_file_ids(self):
 
150
        """Iterate through all file ids, including ids for missing files."""
 
151
        return set(self.inventory)
 
152
 
148
153
    def id2path(self, file_id):
149
154
        """Return the path for a file id.
150
155
 
154
159
 
155
160
    def is_control_filename(self, filename):
156
161
        """True if filename is the name of a control file in this tree.
157
 
        
 
162
 
158
163
        :param filename: A filename within the tree. This is a relative path
159
164
        from the root of this tree.
160
165
 
165
170
        return self.bzrdir.is_control_filename(filename)
166
171
 
167
172
    @needs_read_lock
168
 
    def iter_entries_by_dir(self, specific_file_ids=None):
 
173
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
169
174
        """Walk the tree in 'by_dir' order.
170
175
 
171
 
        This will yield each entry in the tree as a (path, entry) tuple. The
172
 
        order that they are yielded is: the contents of a directory are 
173
 
        preceeded by the parent of a directory, and all the contents of a 
174
 
        directory are grouped together.
 
176
        This will yield each entry in the tree as a (path, entry) tuple.
 
177
        The order that they are yielded is:
 
178
 
 
179
        Directories are walked in a depth-first lexicographical order,
 
180
        however, whenever a directory is reached, all of its direct child
 
181
        nodes are yielded in  lexicographical order before yielding the
 
182
        grandchildren.
 
183
 
 
184
        For example, in the tree::
 
185
 
 
186
           a/
 
187
             b/
 
188
               c
 
189
             d/
 
190
               e
 
191
           f/
 
192
             g
 
193
 
 
194
        The yield order (ignoring root) would be::
 
195
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
 
196
 
 
197
        :param yield_parents: If True, yield the parents from the root leading
 
198
            down to specific_file_ids that have been requested. This has no
 
199
            impact if specific_file_ids is None.
175
200
        """
176
201
        return self.inventory.iter_entries_by_dir(
177
 
            specific_file_ids=specific_file_ids)
 
202
            specific_file_ids=specific_file_ids, yield_parents=yield_parents)
178
203
 
179
204
    def iter_references(self):
180
 
        for path, entry in self.iter_entries_by_dir():
181
 
            if entry.kind == 'tree-reference':
182
 
                yield path, entry.file_id
 
205
        if self.supports_tree_reference():
 
206
            for path, entry in self.iter_entries_by_dir():
 
207
                if entry.kind == 'tree-reference':
 
208
                    yield path, entry.file_id
183
209
 
184
210
    def kind(self, file_id):
185
211
        raise NotImplementedError("Tree subclass %s must implement kind"
186
212
            % self.__class__.__name__)
187
213
 
 
214
    def stored_kind(self, file_id):
 
215
        """File kind stored for this file_id.
 
216
 
 
217
        May not match kind on disk for working trees.  Always available
 
218
        for versioned files, even when the file itself is missing.
 
219
        """
 
220
        return self.kind(file_id)
 
221
 
188
222
    def path_content_summary(self, path):
189
223
        """Get a summary of the information about path.
190
 
        
 
224
 
 
225
        All the attributes returned are for the canonical form, not the
 
226
        convenient form (if content filters are in use.)
 
227
 
191
228
        :param path: A relative path within the tree.
192
229
        :return: A tuple containing kind, size, exec, sha1-or-link.
193
230
            Kind is always present (see tree.kind()).
194
 
            size is present if kind is file, None otherwise.
 
231
            size is present if kind is file and the size of the 
 
232
                canonical form can be cheaply determined, None otherwise.
195
233
            exec is None unless kind is file and the platform supports the 'x'
196
234
                bit.
197
235
            sha1-or-link is the link target if kind is symlink, or the sha1 if
220
258
 
221
259
    def _get_inventory(self):
222
260
        return self._inventory
223
 
    
 
261
 
224
262
    def get_file(self, file_id, path=None):
225
263
        """Return a file object for the file file_id in the tree.
226
 
        
 
264
 
227
265
        If both file_id and path are defined, it is implementation defined as
228
266
        to which one is used.
229
267
        """
230
268
        raise NotImplementedError(self.get_file)
231
269
 
 
270
    def get_file_with_stat(self, file_id, path=None):
 
271
        """Get a file handle and stat object for file_id.
 
272
 
 
273
        The default implementation returns (self.get_file, None) for backwards
 
274
        compatibility.
 
275
 
 
276
        :param file_id: The file id to read.
 
277
        :param path: The path of the file, if it is known.
 
278
        :return: A tuple (file_handle, stat_value_or_None). If the tree has
 
279
            no stat facility, or need for a stat cache feedback during commit,
 
280
            it may return None for the second element of the tuple.
 
281
        """
 
282
        return (self.get_file(file_id, path), None)
 
283
 
 
284
    def get_file_text(self, file_id, path=None):
 
285
        """Return the byte content of a file.
 
286
 
 
287
        :param file_id: The file_id of the file.
 
288
        :param path: The path of the file.
 
289
        If both file_id and path are supplied, an implementation may use
 
290
        either one.
 
291
        """
 
292
        my_file = self.get_file(file_id, path)
 
293
        try:
 
294
            return my_file.read()
 
295
        finally:
 
296
            my_file.close()
 
297
 
 
298
    def get_file_lines(self, file_id, path=None):
 
299
        """Return the content of a file, as lines.
 
300
 
 
301
        :param file_id: The file_id of the file.
 
302
        :param path: The path of the file.
 
303
        If both file_id and path are supplied, an implementation may use
 
304
        either one.
 
305
        """
 
306
        return osutils.split_lines(self.get_file_text(file_id, path))
 
307
 
232
308
    def get_file_mtime(self, file_id, path=None):
233
309
        """Return the modification time for a file.
234
310
 
238
314
        """
239
315
        raise NotImplementedError(self.get_file_mtime)
240
316
 
 
317
    def get_file_size(self, file_id):
 
318
        """Return the size of a file in bytes.
 
319
 
 
320
        This applies only to regular files.  If invoked on directories or
 
321
        symlinks, it will return None.
 
322
        :param file_id: The file-id of the file
 
323
        """
 
324
        raise NotImplementedError(self.get_file_size)
 
325
 
241
326
    def get_file_by_path(self, path):
242
327
        return self.get_file(self._inventory.path2id(path), path)
243
328
 
277
362
        """
278
363
        raise NotImplementedError(self.get_symlink_target)
279
364
 
 
365
    def get_canonical_inventory_paths(self, paths):
 
366
        """Like get_canonical_inventory_path() but works on multiple items.
 
367
 
 
368
        :param paths: A sequence of paths relative to the root of the tree.
 
369
        :return: A list of paths, with each item the corresponding input path
 
370
        adjusted to account for existing elements that match case
 
371
        insensitively.
 
372
        """
 
373
        return list(self._yield_canonical_inventory_paths(paths))
 
374
 
 
375
    def get_canonical_inventory_path(self, path):
 
376
        """Returns the first inventory item that case-insensitively matches path.
 
377
 
 
378
        If a path matches exactly, it is returned. If no path matches exactly
 
379
        but more than one path matches case-insensitively, it is implementation
 
380
        defined which is returned.
 
381
 
 
382
        If no path matches case-insensitively, the input path is returned, but
 
383
        with as many path entries that do exist changed to their canonical
 
384
        form.
 
385
 
 
386
        If you need to resolve many names from the same tree, you should
 
387
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
388
 
 
389
        :param path: A paths relative to the root of the tree.
 
390
        :return: The input path adjusted to account for existing elements
 
391
        that match case insensitively.
 
392
        """
 
393
        return self._yield_canonical_inventory_paths([path]).next()
 
394
 
 
395
    def _yield_canonical_inventory_paths(self, paths):
 
396
        for path in paths:
 
397
            # First, if the path as specified exists exactly, just use it.
 
398
            if self.path2id(path) is not None:
 
399
                yield path
 
400
                continue
 
401
            # go walkin...
 
402
            cur_id = self.get_root_id()
 
403
            cur_path = ''
 
404
            bit_iter = iter(path.split("/"))
 
405
            for elt in bit_iter:
 
406
                lelt = elt.lower()
 
407
                new_path = None
 
408
                for child in self.iter_children(cur_id):
 
409
                    try:
 
410
                        # XXX: it seem like if the child is known to be in the
 
411
                        # tree, we shouldn't need to go from its id back to
 
412
                        # its path -- mbp 2010-02-11
 
413
                        #
 
414
                        # XXX: it seems like we could be more efficient
 
415
                        # by just directly looking up the original name and
 
416
                        # only then searching all children; also by not
 
417
                        # chopping paths so much. -- mbp 2010-02-11
 
418
                        child_base = os.path.basename(self.id2path(child))
 
419
                        if (child_base == elt):
 
420
                            # if we found an exact match, we can stop now; if
 
421
                            # we found an approximate match we need to keep
 
422
                            # searching because there might be an exact match
 
423
                            # later.  
 
424
                            cur_id = child
 
425
                            new_path = osutils.pathjoin(cur_path, child_base)
 
426
                            break
 
427
                        elif child_base.lower() == lelt:
 
428
                            cur_id = child
 
429
                            new_path = osutils.pathjoin(cur_path, child_base)
 
430
                    except NoSuchId:
 
431
                        # before a change is committed we can see this error...
 
432
                        continue
 
433
                if new_path:
 
434
                    cur_path = new_path
 
435
                else:
 
436
                    # got to the end of this directory and no entries matched.
 
437
                    # Return what matched so far, plus the rest as specified.
 
438
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
439
                    break
 
440
            yield cur_path
 
441
        # all done.
 
442
 
280
443
    def get_root_id(self):
281
444
        """Return the file_id for the root of this tree."""
282
445
        raise NotImplementedError(self.get_root_id)
283
446
 
284
 
    def annotate_iter(self, file_id):
 
447
    def annotate_iter(self, file_id,
 
448
                      default_revision=_mod_revision.CURRENT_REVISION):
285
449
        """Return an iterator of revision_id, line tuples.
286
450
 
287
451
        For working trees (and mutable trees in general), the special
288
452
        revision_id 'current:' will be used for lines that are new in this
289
453
        tree, e.g. uncommitted changes.
290
454
        :param file_id: The file to produce an annotated version from
 
455
        :param default_revision: For lines that don't match a basis, mark them
 
456
            with this revision id. Not all implementations will make use of
 
457
            this value.
291
458
        """
292
459
        raise NotImplementedError(self.annotate_iter)
293
460
 
294
461
    def _get_plan_merge_data(self, file_id, other, base):
295
 
        from bzrlib import merge, versionedfile
 
462
        from bzrlib import versionedfile
296
463
        vf = versionedfile._PlanMergeVersionedFile(file_id)
297
464
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
298
465
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
328
495
        return vf.plan_lca_merge(last_revision_a, last_revision_b,
329
496
                                 last_revision_base)
330
497
 
 
498
    def _iter_parent_trees(self):
 
499
        """Iterate through parent trees, defaulting to Tree.revision_tree."""
 
500
        for revision_id in self.get_parent_ids():
 
501
            try:
 
502
                yield self.revision_tree(revision_id)
 
503
            except errors.NoSuchRevisionInTree:
 
504
                yield self.repository.revision_tree(revision_id)
 
505
 
 
506
    @staticmethod
 
507
    def _file_revision(revision_tree, file_id):
 
508
        """Determine the revision associated with a file in a given tree."""
 
509
        revision_tree.lock_read()
 
510
        try:
 
511
            return revision_tree.inventory[file_id].revision
 
512
        finally:
 
513
            revision_tree.unlock()
 
514
 
331
515
    def _get_file_revision(self, file_id, vf, tree_revision):
332
 
        def file_revision(revision_tree):
333
 
            revision_tree.lock_read()
334
 
            try:
335
 
                return revision_tree.inventory[file_id].revision
336
 
            finally:
337
 
                revision_tree.unlock()
338
 
 
339
 
        def iter_parent_trees():
340
 
            for revision_id in self.get_parent_ids():
341
 
                try:
342
 
                    yield self.revision_tree(revision_id)
343
 
                except:
344
 
                    yield self.repository.revision_tree(revision_id)
345
 
 
346
 
        if getattr(self, '_get_weave', None) is None:
 
516
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
 
517
 
 
518
        if getattr(self, '_repository', None) is None:
347
519
            last_revision = tree_revision
348
 
            parent_revisions = [file_revision(t) for t in iter_parent_trees()]
349
 
            vf.add_lines(last_revision, parent_revisions,
350
 
                         self.get_file(file_id).readlines())
 
520
            parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
 
521
                self._iter_parent_trees()]
 
522
            vf.add_lines((file_id, last_revision), parent_keys,
 
523
                         self.get_file_lines(file_id))
351
524
            repo = self.branch.repository
352
 
            transaction = repo.get_transaction()
353
 
            base_vf = repo.weave_store.get_weave(file_id, transaction)
 
525
            base_vf = repo.texts
354
526
        else:
355
 
            last_revision = file_revision(self)
356
 
            base_vf = self._get_weave(file_id)
357
 
        vf.fallback_versionedfiles.append(base_vf)
 
527
            last_revision = self._file_revision(self, file_id)
 
528
            base_vf = self._repository.texts
 
529
        if base_vf not in vf.fallback_versionedfiles:
 
530
            vf.fallback_versionedfiles.append(base_vf)
358
531
        return last_revision
359
532
 
360
533
    inventory = property(_get_inventory,
362
535
 
363
536
    def _check_retrieved(self, ie, f):
364
537
        if not __debug__:
365
 
            return  
 
538
            return
366
539
        fp = fingerprint_file(f)
367
540
        f.seek(0)
368
 
        
 
541
 
369
542
        if ie.text_size is not None:
370
543
            if ie.text_size != fp['size']:
371
544
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
386
559
 
387
560
    def paths2ids(self, paths, trees=[], require_versioned=True):
388
561
        """Return all the ids that can be reached by walking from paths.
389
 
        
 
562
 
390
563
        Each path is looked up in this tree and any extras provided in
391
564
        trees, and this is repeated recursively: the children in an extra tree
392
565
        of a directory that has been renamed under a provided path in this tree
403
576
        """
404
577
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
405
578
 
406
 
    def print_file(self, file_id):
407
 
        """Print file with id `file_id` to stdout."""
408
 
        import sys
409
 
        sys.stdout.write(self.get_file_text(file_id))
 
579
    def iter_children(self, file_id):
 
580
        entry = self.iter_entries_by_dir([file_id]).next()[1]
 
581
        for child in getattr(entry, 'children', {}).itervalues():
 
582
            yield child.file_id
410
583
 
411
584
    def lock_read(self):
 
585
        """Lock this tree for multiple read only operations.
 
586
        
 
587
        :return: A bzrlib.lock.LogicalLockResult.
 
588
        """
412
589
        pass
413
590
 
414
591
    def revision_tree(self, revision_id):
416
593
 
417
594
        The intention of this method is to allow access to possibly cached
418
595
        tree data. Implementors of this method should raise NoSuchRevision if
419
 
        the tree is not locally available, even if they could obtain the 
420
 
        tree via a repository or some other means. Callers are responsible 
 
596
        the tree is not locally available, even if they could obtain the
 
597
        tree via a repository or some other means. Callers are responsible
421
598
        for finding the ultimate source for a revision tree.
422
599
 
423
600
        :param revision_id: The revision_id of the requested tree.
428
605
 
429
606
    def unknowns(self):
430
607
        """What files are present in this tree and unknown.
431
 
        
 
608
 
432
609
        :return: an iterator over the unknown files.
433
610
        """
434
611
        return iter([])
442
619
        :return: set of paths.
443
620
        """
444
621
        # NB: we specifically *don't* call self.has_filename, because for
445
 
        # WorkingTrees that can indicate files that exist on disk but that 
 
622
        # WorkingTrees that can indicate files that exist on disk but that
446
623
        # are not versioned.
447
624
        pred = self.inventory.has_filename
448
625
        return set((p for p in paths if not pred(p)))
453
630
        This yields all the data about the contents of a directory at a time.
454
631
        After each directory has been yielded, if the caller has mutated the
455
632
        list to exclude some directories, they are then not descended into.
456
 
        
 
633
 
457
634
        The data yielded is of the form:
458
635
        ((directory-relpath, directory-path-from-root, directory-fileid),
459
 
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id, 
 
636
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id,
460
637
          versioned_kind), ...]),
461
638
         - directory-relpath is the containing dirs relpath from prefix
462
639
         - directory-path-from-root is the containing dirs path from /
469
646
         - lstat is the stat data *if* the file was statted.
470
647
         - path_from_tree_root is the path from the root of the tree.
471
648
         - file_id is the file_id if the entry is versioned.
472
 
         - versioned_kind is the kind of the file as last recorded in the 
 
649
         - versioned_kind is the kind of the file as last recorded in the
473
650
           versioning system. If 'unknown' the file is not versioned.
474
651
        One of 'kind' and 'versioned_kind' must not be 'unknown'.
475
652
 
480
657
        """
481
658
        raise NotImplementedError(self.walkdirs)
482
659
 
483
 
 
484
 
class EmptyTree(Tree):
485
 
 
486
 
    def __init__(self):
487
 
        self._inventory = Inventory(root_id=None)
488
 
        symbol_versioning.warn('EmptyTree is deprecated as of bzr 0.9 please'
489
 
                               ' use repository.revision_tree instead.',
490
 
                               DeprecationWarning, stacklevel=2)
491
 
 
492
 
    def get_parent_ids(self):
493
 
        return []
494
 
 
495
 
    def get_symlink_target(self, file_id):
496
 
        return None
497
 
 
498
 
    def has_filename(self, filename):
 
660
    def supports_content_filtering(self):
499
661
        return False
500
662
 
501
 
    def kind(self, file_id):
502
 
        assert self._inventory[file_id].kind == "directory"
503
 
        return "directory"
504
 
 
505
 
    def list_files(self, include_root=False):
506
 
        return iter([])
507
 
    
508
 
    def __contains__(self, file_id):
509
 
        return (file_id in self._inventory)
510
 
 
511
 
    def get_file_sha1(self, file_id, path=None, stat_value=None):
512
 
        return None
 
663
    def _content_filter_stack(self, path=None, file_id=None):
 
664
        """The stack of content filters for a path if filtering is supported.
 
665
 
 
666
        Readers will be applied in first-to-last order.
 
667
        Writers will be applied in last-to-first order.
 
668
        Either the path or the file-id needs to be provided.
 
669
 
 
670
        :param path: path relative to the root of the tree
 
671
            or None if unknown
 
672
        :param file_id: file_id or None if unknown
 
673
        :return: the list of filters - [] if there are none
 
674
        """
 
675
        filter_pref_names = filters._get_registered_names()
 
676
        if len(filter_pref_names) == 0:
 
677
            return []
 
678
        if path is None:
 
679
            path = self.id2path(file_id)
 
680
        prefs = self.iter_search_rules([path], filter_pref_names).next()
 
681
        stk = filters._get_filter_stack_for(prefs)
 
682
        if 'filters' in debug.debug_flags:
 
683
            note("*** %s content-filter: %s => %r" % (path,prefs,stk))
 
684
        return stk
 
685
 
 
686
    def _content_filter_stack_provider(self):
 
687
        """A function that returns a stack of ContentFilters.
 
688
 
 
689
        The function takes a path (relative to the top of the tree) and a
 
690
        file-id as parameters.
 
691
 
 
692
        :return: None if content filtering is not supported by this tree.
 
693
        """
 
694
        if self.supports_content_filtering():
 
695
            return lambda path, file_id: \
 
696
                    self._content_filter_stack(path, file_id)
 
697
        else:
 
698
            return None
 
699
 
 
700
    def iter_search_rules(self, path_names, pref_names=None,
 
701
        _default_searcher=None):
 
702
        """Find the preferences for filenames in a tree.
 
703
 
 
704
        :param path_names: an iterable of paths to find attributes for.
 
705
          Paths are given relative to the root of the tree.
 
706
        :param pref_names: the list of preferences to lookup - None for all
 
707
        :param _default_searcher: private parameter to assist testing - don't use
 
708
        :return: an iterator of tuple sequences, one per path-name.
 
709
          See _RulesSearcher.get_items for details on the tuple sequence.
 
710
        """
 
711
        if _default_searcher is None:
 
712
            _default_searcher = rules._per_user_searcher
 
713
        searcher = self._get_rules_searcher(_default_searcher)
 
714
        if searcher is not None:
 
715
            if pref_names is not None:
 
716
                for path in path_names:
 
717
                    yield searcher.get_selected_items(path, pref_names)
 
718
            else:
 
719
                for path in path_names:
 
720
                    yield searcher.get_items(path)
 
721
 
 
722
    def _get_rules_searcher(self, default_searcher):
 
723
        """Get the RulesSearcher for this tree given the default one."""
 
724
        searcher = default_searcher
 
725
        return searcher
513
726
 
514
727
 
515
728
######################################################################
548
761
        # what happened to the file that used to have
549
762
        # this name.  There are two possibilities: either it was
550
763
        # deleted entirely, or renamed.
551
 
        assert old_id
552
764
        if new_inv.has_id(old_id):
553
765
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
554
766
        else:
565
777
 
566
778
    return 'wtf?'
567
779
 
568
 
    
569
780
 
 
781
@deprecated_function(deprecated_in((1, 9, 0)))
570
782
def find_renames(old_inv, new_inv):
571
783
    for file_id in old_inv:
572
784
        if file_id not in new_inv:
575
787
        new_name = new_inv.id2path(file_id)
576
788
        if old_name != new_name:
577
789
            yield (old_name, new_name)
578
 
            
 
790
 
579
791
 
580
792
def find_ids_across_trees(filenames, trees, require_versioned=True):
581
793
    """Find the ids corresponding to specified filenames.
582
 
    
 
794
 
583
795
    All matches in all trees will be used, and all children of matched
584
796
    directories will be used.
585
797
 
599
811
 
600
812
def _find_ids_across_trees(filenames, trees, require_versioned):
601
813
    """Find the ids corresponding to specified filenames.
602
 
    
 
814
 
603
815
    All matches in all trees will be used, but subdirectories are not scanned.
604
816
 
605
817
    :param filenames: The filenames to find file_ids for
626
838
 
627
839
def _find_children_across_trees(specified_ids, trees):
628
840
    """Return a set including specified ids and their children.
629
 
    
 
841
 
630
842
    All matches in all trees will be used.
631
843
 
632
844
    :param trees: The trees to find file_ids within
633
 
    :return: a set containing all specified ids and their children 
 
845
    :return: a set containing all specified ids and their children
634
846
    """
635
847
    interesting_ids = set(specified_ids)
636
848
    pending = interesting_ids
640
852
        new_pending = set()
641
853
        for file_id in pending:
642
854
            for tree in trees:
643
 
                if not tree.has_id(file_id):
 
855
                if not tree.has_or_had_id(file_id):
644
856
                    continue
645
 
                entry = tree.inventory[file_id]
646
 
                for child in getattr(entry, 'children', {}).itervalues():
647
 
                    if child.file_id not in interesting_ids:
648
 
                        new_pending.add(child.file_id)
 
857
                for child_id in tree.iter_children(file_id):
 
858
                    if child_id not in interesting_ids:
 
859
                        new_pending.add(child_id)
649
860
        interesting_ids.update(new_pending)
650
861
        pending = new_pending
651
862
    return interesting_ids
662
873
    will pass through to InterTree as appropriate.
663
874
    """
664
875
 
 
876
    # Formats that will be used to test this InterTree. If both are
 
877
    # None, this InterTree will not be tested (e.g. because a complex
 
878
    # setup is required)
 
879
    _matching_from_tree_format = None
 
880
    _matching_to_tree_format = None
 
881
 
665
882
    _optimisers = []
666
883
 
 
884
    def _changes_from_entries(self, source_entry, target_entry,
 
885
        source_path=None, target_path=None):
 
886
        """Generate a iter_changes tuple between source_entry and target_entry.
 
887
 
 
888
        :param source_entry: An inventory entry from self.source, or None.
 
889
        :param target_entry: An inventory entry from self.target, or None.
 
890
        :param source_path: The path of source_entry, if known. If not known
 
891
            it will be looked up.
 
892
        :param target_path: The path of target_entry, if known. If not known
 
893
            it will be looked up.
 
894
        :return: A tuple, item 0 of which is an iter_changes result tuple, and
 
895
            item 1 is True if there are any changes in the result tuple.
 
896
        """
 
897
        if source_entry is None:
 
898
            if target_entry is None:
 
899
                return None
 
900
            file_id = target_entry.file_id
 
901
        else:
 
902
            file_id = source_entry.file_id
 
903
        if source_entry is not None:
 
904
            source_versioned = True
 
905
            source_name = source_entry.name
 
906
            source_parent = source_entry.parent_id
 
907
            if source_path is None:
 
908
                source_path = self.source.id2path(file_id)
 
909
            source_kind, source_executable, source_stat = \
 
910
                self.source._comparison_data(source_entry, source_path)
 
911
        else:
 
912
            source_versioned = False
 
913
            source_name = None
 
914
            source_parent = None
 
915
            source_kind = None
 
916
            source_executable = None
 
917
        if target_entry is not None:
 
918
            target_versioned = True
 
919
            target_name = target_entry.name
 
920
            target_parent = target_entry.parent_id
 
921
            if target_path is None:
 
922
                target_path = self.target.id2path(file_id)
 
923
            target_kind, target_executable, target_stat = \
 
924
                self.target._comparison_data(target_entry, target_path)
 
925
        else:
 
926
            target_versioned = False
 
927
            target_name = None
 
928
            target_parent = None
 
929
            target_kind = None
 
930
            target_executable = None
 
931
        versioned = (source_versioned, target_versioned)
 
932
        kind = (source_kind, target_kind)
 
933
        changed_content = False
 
934
        if source_kind != target_kind:
 
935
            changed_content = True
 
936
        elif source_kind == 'file':
 
937
            if (self.source.get_file_sha1(file_id, source_path, source_stat) !=
 
938
                self.target.get_file_sha1(file_id, target_path, target_stat)):
 
939
                changed_content = True
 
940
        elif source_kind == 'symlink':
 
941
            if (self.source.get_symlink_target(file_id) !=
 
942
                self.target.get_symlink_target(file_id)):
 
943
                changed_content = True
 
944
            # XXX: Yes, the indentation below is wrong. But fixing it broke
 
945
            # test_merge.TestMergerEntriesLCAOnDisk.
 
946
            # test_nested_tree_subtree_renamed_and_modified. We'll wait for
 
947
            # the fix from bzr.dev -- vila 2009026
 
948
            elif source_kind == 'tree-reference':
 
949
                if (self.source.get_reference_revision(file_id, source_path)
 
950
                    != self.target.get_reference_revision(file_id, target_path)):
 
951
                    changed_content = True
 
952
        parent = (source_parent, target_parent)
 
953
        name = (source_name, target_name)
 
954
        executable = (source_executable, target_executable)
 
955
        if (changed_content is not False or versioned[0] != versioned[1]
 
956
            or parent[0] != parent[1] or name[0] != name[1] or
 
957
            executable[0] != executable[1]):
 
958
            changes = True
 
959
        else:
 
960
            changes = False
 
961
        return (file_id, (source_path, target_path), changed_content,
 
962
                versioned, parent, name, kind, executable), changes
 
963
 
667
964
    @needs_read_lock
668
965
    def compare(self, want_unchanged=False, specific_files=None,
669
966
        extra_trees=None, require_versioned=False, include_root=False,
684
981
            a PathsNotVersionedError will be thrown.
685
982
        :param want_unversioned: Scan for unversioned paths.
686
983
        """
687
 
        # NB: show_status depends on being able to pass in non-versioned files
688
 
        # and report them as unknown
689
984
        trees = (self.source,)
690
985
        if extra_trees is not None:
691
986
            trees = trees + tuple(extra_trees)
706
1001
            require_versioned=require_versioned,
707
1002
            want_unversioned=want_unversioned)
708
1003
 
709
 
    def _iter_changes(self, include_unchanged=False,
 
1004
    def iter_changes(self, include_unchanged=False,
710
1005
                      specific_files=None, pb=None, extra_trees=[],
711
1006
                      require_versioned=True, want_unversioned=False):
712
1007
        """Generate an iterator of changes between trees.
732
1027
        :param require_versioned: Raise errors.PathsNotVersionedError if a
733
1028
            path in the specific_files list is not versioned in one of
734
1029
            source, target or extra_trees.
 
1030
        :param specific_files: An optional list of file paths to restrict the
 
1031
            comparison to. When mapping filenames to ids, all matches in all
 
1032
            trees (including optional extra_trees) are used, and all children
 
1033
            of matched directories are included. The parents in the target tree
 
1034
            of the specific files up to and including the root of the tree are
 
1035
            always evaluated for changes too.
735
1036
        :param want_unversioned: Should unversioned files be returned in the
736
1037
            output. An unversioned file is defined as one with (False, False)
737
1038
            for the versioned pair.
738
1039
        """
739
 
        result = []
740
1040
        lookup_trees = [self.source]
741
1041
        if extra_trees:
742
1042
             lookup_trees.extend(extra_trees)
 
1043
        # The ids of items we need to examine to insure delta consistency.
 
1044
        precise_file_ids = set()
 
1045
        changed_file_ids = []
743
1046
        if specific_files == []:
744
1047
            specific_file_ids = []
745
1048
        else:
746
1049
            specific_file_ids = self.target.paths2ids(specific_files,
747
1050
                lookup_trees, require_versioned=require_versioned)
 
1051
        if specific_files is not None:
 
1052
            # reparented or added entries must have their parents included
 
1053
            # so that valid deltas can be created. The seen_parents set
 
1054
            # tracks the parents that we need to have.
 
1055
            # The seen_dirs set tracks directory entries we've yielded.
 
1056
            # After outputting version object in to_entries we set difference
 
1057
            # the two seen sets and start checking parents.
 
1058
            seen_parents = set()
 
1059
            seen_dirs = set()
748
1060
        if want_unversioned:
749
1061
            all_unversioned = sorted([(p.split('/'), p) for p in
750
1062
                                     self.target.extras()
754
1066
        else:
755
1067
            all_unversioned = deque()
756
1068
        to_paths = {}
757
 
        from_entries_by_dir = list(self.source.inventory.iter_entries_by_dir(
 
1069
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
758
1070
            specific_file_ids=specific_file_ids))
759
1071
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
760
 
        to_entries_by_dir = list(self.target.inventory.iter_entries_by_dir(
 
1072
        to_entries_by_dir = list(self.target.iter_entries_by_dir(
761
1073
            specific_file_ids=specific_file_ids))
762
1074
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
763
1075
        entry_count = 0
764
 
        # the unversioned path lookup only occurs on real trees - where there 
 
1076
        # the unversioned path lookup only occurs on real trees - where there
765
1077
        # can be extras. So the fake_entry is solely used to look up
766
1078
        # executable it values when execute is not supported.
767
1079
        fake_entry = InventoryFile('unused', 'unused', 'unused')
768
 
        for to_path, to_entry in to_entries_by_dir:
769
 
            while all_unversioned and all_unversioned[0][0] < to_path.split('/'):
 
1080
        for target_path, target_entry in to_entries_by_dir:
 
1081
            while (all_unversioned and
 
1082
                all_unversioned[0][0] < target_path.split('/')):
770
1083
                unversioned_path = all_unversioned.popleft()
771
 
                to_kind, to_executable, to_stat = \
 
1084
                target_kind, target_executable, target_stat = \
772
1085
                    self.target._comparison_data(fake_entry, unversioned_path[1])
773
1086
                yield (None, (None, unversioned_path[1]), True, (False, False),
774
1087
                    (None, None),
775
1088
                    (None, unversioned_path[0][-1]),
776
 
                    (None, to_kind),
777
 
                    (None, to_executable))
778
 
            file_id = to_entry.file_id
779
 
            to_paths[file_id] = to_path
 
1089
                    (None, target_kind),
 
1090
                    (None, target_executable))
 
1091
            source_path, source_entry = from_data.get(target_entry.file_id,
 
1092
                (None, None))
 
1093
            result, changes = self._changes_from_entries(source_entry,
 
1094
                target_entry, source_path=source_path, target_path=target_path)
 
1095
            to_paths[result[0]] = result[1][1]
780
1096
            entry_count += 1
781
 
            changed_content = False
782
 
            from_path, from_entry = from_data.get(file_id, (None, None))
783
 
            from_versioned = (from_entry is not None)
784
 
            if from_entry is not None:
785
 
                from_versioned = True
786
 
                from_name = from_entry.name
787
 
                from_parent = from_entry.parent_id
788
 
                from_kind, from_executable, from_stat = \
789
 
                    self.source._comparison_data(from_entry, from_path)
 
1097
            if result[3][0]:
790
1098
                entry_count += 1
791
 
            else:
792
 
                from_versioned = False
793
 
                from_kind = None
794
 
                from_parent = None
795
 
                from_name = None
796
 
                from_executable = None
797
 
            versioned = (from_versioned, True)
798
 
            to_kind, to_executable, to_stat = \
799
 
                self.target._comparison_data(to_entry, to_path)
800
 
            kind = (from_kind, to_kind)
801
 
            if kind[0] != kind[1]:
802
 
                changed_content = True
803
 
            elif from_kind == 'file':
804
 
                from_size = self.source._file_size(from_entry, from_stat)
805
 
                to_size = self.target._file_size(to_entry, to_stat)
806
 
                if from_size != to_size:
807
 
                    changed_content = True
808
 
                elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
809
 
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
810
 
                    changed_content = True
811
 
            elif from_kind == 'symlink':
812
 
                if (self.source.get_symlink_target(file_id) !=
813
 
                    self.target.get_symlink_target(file_id)):
814
 
                    changed_content = True
815
 
                elif from_kind == 'tree-reference':
816
 
                    if (self.source.get_reference_revision(file_id, from_path)
817
 
                        != self.target.get_reference_revision(file_id, to_path)):
818
 
                        changed_content = True 
819
 
            parent = (from_parent, to_entry.parent_id)
820
 
            name = (from_name, to_entry.name)
821
 
            executable = (from_executable, to_executable)
822
1099
            if pb is not None:
823
1100
                pb.update('comparing files', entry_count, num_entries)
824
 
            if (changed_content is not False or versioned[0] != versioned[1]
825
 
                or parent[0] != parent[1] or name[0] != name[1] or 
826
 
                executable[0] != executable[1] or include_unchanged):
827
 
                yield (file_id, (from_path, to_path), changed_content,
828
 
                    versioned, parent, name, kind, executable)
829
 
 
 
1101
            if changes or include_unchanged:
 
1102
                if specific_file_ids is not None:
 
1103
                    new_parent_id = result[4][1]
 
1104
                    precise_file_ids.add(new_parent_id)
 
1105
                    changed_file_ids.append(result[0])
 
1106
                yield result
 
1107
            # Ensure correct behaviour for reparented/added specific files.
 
1108
            if specific_files is not None:
 
1109
                # Record output dirs
 
1110
                if result[6][1] == 'directory':
 
1111
                    seen_dirs.add(result[0])
 
1112
                # Record parents of reparented/added entries.
 
1113
                versioned = result[3]
 
1114
                parents = result[4]
 
1115
                if not versioned[0] or parents[0] != parents[1]:
 
1116
                    seen_parents.add(parents[1])
830
1117
        while all_unversioned:
831
1118
            # yield any trailing unversioned paths
832
1119
            unversioned_path = all_unversioned.popleft()
837
1124
                (None, unversioned_path[0][-1]),
838
1125
                (None, to_kind),
839
1126
                (None, to_executable))
840
 
 
841
 
        def get_to_path(to_entry):
842
 
            if to_entry.parent_id is None:
843
 
                to_path = '' # the root
844
 
            else:
845
 
                if to_entry.parent_id not in to_paths:
846
 
                    # recurse up
847
 
                    return get_to_path(self.target.inventory[to_entry.parent_id])
848
 
                to_path = osutils.pathjoin(to_paths[to_entry.parent_id],
849
 
                                           to_entry.name)
850
 
            to_paths[to_entry.file_id] = to_path
851
 
            return to_path
852
 
 
 
1127
        # Yield all remaining source paths
853
1128
        for path, from_entry in from_entries_by_dir:
854
1129
            file_id = from_entry.file_id
855
1130
            if file_id in to_paths:
856
1131
                # already returned
857
1132
                continue
858
 
            if not file_id in self.target.inventory:
 
1133
            if not self.target.has_id(file_id):
859
1134
                # common case - paths we have not emitted are not present in
860
1135
                # target.
861
1136
                to_path = None
862
1137
            else:
863
 
                to_path = get_to_path(self.target.inventory[file_id])
 
1138
                to_path = self.target.id2path(file_id)
864
1139
            entry_count += 1
865
1140
            if pb is not None:
866
1141
                pb.update('comparing files', entry_count, num_entries)
871
1146
                self.source._comparison_data(from_entry, path)
872
1147
            kind = (from_kind, None)
873
1148
            executable = (from_executable, None)
874
 
            changed_content = True
 
1149
            changed_content = from_kind is not None
875
1150
            # the parent's path is necessarily known at this point.
 
1151
            changed_file_ids.append(file_id)
876
1152
            yield(file_id, (path, to_path), changed_content, versioned, parent,
877
1153
                  name, kind, executable)
878
 
 
879
 
 
880
 
# This was deprecated before 0.12, but did not have an official warning
881
 
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
882
 
def RevisionTree(*args, **kwargs):
883
 
    """RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
884
 
 
885
 
    Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
886
 
    bzr 0.12.
887
 
    """
888
 
    from bzrlib.revisiontree import RevisionTree as _RevisionTree
889
 
    return _RevisionTree(*args, **kwargs)
890
 
 
891
 
 
 
1154
        changed_file_ids = set(changed_file_ids)
 
1155
        if specific_file_ids is not None:
 
1156
            for result in self._handle_precise_ids(precise_file_ids,
 
1157
                changed_file_ids):
 
1158
                yield result
 
1159
 
 
1160
    def _get_entry(self, tree, file_id):
 
1161
        """Get an inventory entry from a tree, with missing entries as None.
 
1162
 
 
1163
        If the tree raises NotImplementedError on accessing .inventory, then
 
1164
        this is worked around using iter_entries_by_dir on just the file id
 
1165
        desired.
 
1166
 
 
1167
        :param tree: The tree to lookup the entry in.
 
1168
        :param file_id: The file_id to lookup.
 
1169
        """
 
1170
        try:
 
1171
            inventory = tree.inventory
 
1172
        except NotImplementedError:
 
1173
            # No inventory available.
 
1174
            try:
 
1175
                iterator = tree.iter_entries_by_dir(specific_file_ids=[file_id])
 
1176
                return iterator.next()[1]
 
1177
            except StopIteration:
 
1178
                return None
 
1179
        else:
 
1180
            try:
 
1181
                return inventory[file_id]
 
1182
            except errors.NoSuchId:
 
1183
                return None
 
1184
 
 
1185
    def _handle_precise_ids(self, precise_file_ids, changed_file_ids,
 
1186
        discarded_changes=None):
 
1187
        """Fill out a partial iter_changes to be consistent.
 
1188
 
 
1189
        :param precise_file_ids: The file ids of parents that were seen during
 
1190
            the iter_changes.
 
1191
        :param changed_file_ids: The file ids of already emitted items.
 
1192
        :param discarded_changes: An optional dict of precalculated
 
1193
            iter_changes items which the partial iter_changes had not output
 
1194
            but had calculated.
 
1195
        :return: A generator of iter_changes items to output.
 
1196
        """
 
1197
        # process parents of things that had changed under the users
 
1198
        # requested paths to prevent incorrect paths or parent ids which
 
1199
        # aren't in the tree.
 
1200
        while precise_file_ids:
 
1201
            precise_file_ids.discard(None)
 
1202
            # Don't emit file_ids twice
 
1203
            precise_file_ids.difference_update(changed_file_ids)
 
1204
            if not precise_file_ids:
 
1205
                break
 
1206
            # If the there was something at a given output path in source, we
 
1207
            # have to include the entry from source in the delta, or we would
 
1208
            # be putting this entry into a used path.
 
1209
            paths = []
 
1210
            for parent_id in precise_file_ids:
 
1211
                try:
 
1212
                    paths.append(self.target.id2path(parent_id))
 
1213
                except errors.NoSuchId:
 
1214
                    # This id has been dragged in from the source by delta
 
1215
                    # expansion and isn't present in target at all: we don't
 
1216
                    # need to check for path collisions on it.
 
1217
                    pass
 
1218
            for path in paths:
 
1219
                old_id = self.source.path2id(path)
 
1220
                precise_file_ids.add(old_id)
 
1221
            precise_file_ids.discard(None)
 
1222
            current_ids = precise_file_ids
 
1223
            precise_file_ids = set()
 
1224
            # We have to emit all of precise_file_ids that have been altered.
 
1225
            # We may have to output the children of some of those ids if any
 
1226
            # directories have stopped being directories.
 
1227
            for file_id in current_ids:
 
1228
                # Examine file_id
 
1229
                if discarded_changes:
 
1230
                    result = discarded_changes.get(file_id)
 
1231
                    old_entry = None
 
1232
                else:
 
1233
                    result = None
 
1234
                if result is None:
 
1235
                    old_entry = self._get_entry(self.source, file_id)
 
1236
                    new_entry = self._get_entry(self.target, file_id)
 
1237
                    result, changes = self._changes_from_entries(
 
1238
                        old_entry, new_entry)
 
1239
                else:
 
1240
                    changes = True
 
1241
                # Get this parents parent to examine.
 
1242
                new_parent_id = result[4][1]
 
1243
                precise_file_ids.add(new_parent_id)
 
1244
                if changes:
 
1245
                    if (result[6][0] == 'directory' and
 
1246
                        result[6][1] != 'directory'):
 
1247
                        # This stopped being a directory, the old children have
 
1248
                        # to be included.
 
1249
                        if old_entry is None:
 
1250
                            # Reusing a discarded change.
 
1251
                            old_entry = self._get_entry(self.source, file_id)
 
1252
                        for child in old_entry.children.values():
 
1253
                            precise_file_ids.add(child.file_id)
 
1254
                    changed_file_ids.add(result[0])
 
1255
                    yield result
 
1256
 
 
1257
 
 
1258
class MultiWalker(object):
 
1259
    """Walk multiple trees simultaneously, getting combined results."""
 
1260
 
 
1261
    # Note: This could be written to not assume you can do out-of-order
 
1262
    #       lookups. Instead any nodes that don't match in all trees could be
 
1263
    #       marked as 'deferred', and then returned in the final cleanup loop.
 
1264
    #       For now, I think it is "nicer" to return things as close to the
 
1265
    #       "master_tree" order as we can.
 
1266
 
 
1267
    def __init__(self, master_tree, other_trees):
 
1268
        """Create a new MultiWalker.
 
1269
 
 
1270
        All trees being walked must implement "iter_entries_by_dir()", such
 
1271
        that they yield (path, object) tuples, where that object will have a
 
1272
        '.file_id' member, that can be used to check equality.
 
1273
 
 
1274
        :param master_tree: All trees will be 'slaved' to the master_tree such
 
1275
            that nodes in master_tree will be used as 'first-pass' sync points.
 
1276
            Any nodes that aren't in master_tree will be merged in a second
 
1277
            pass.
 
1278
        :param other_trees: A list of other trees to walk simultaneously.
 
1279
        """
 
1280
        self._master_tree = master_tree
 
1281
        self._other_trees = other_trees
 
1282
 
 
1283
        # Keep track of any nodes that were properly processed just out of
 
1284
        # order, that way we don't return them at the end, we don't have to
 
1285
        # track *all* processed file_ids, just the out-of-order ones
 
1286
        self._out_of_order_processed = set()
 
1287
 
 
1288
    @staticmethod
 
1289
    def _step_one(iterator):
 
1290
        """Step an iter_entries_by_dir iterator.
 
1291
 
 
1292
        :return: (has_more, path, ie)
 
1293
            If has_more is False, path and ie will be None.
 
1294
        """
 
1295
        try:
 
1296
            path, ie = iterator.next()
 
1297
        except StopIteration:
 
1298
            return False, None, None
 
1299
        else:
 
1300
            return True, path, ie
 
1301
 
 
1302
    @staticmethod
 
1303
    def _cmp_path_by_dirblock(path1, path2):
 
1304
        """Compare two paths based on what directory they are in.
 
1305
 
 
1306
        This generates a sort order, such that all children of a directory are
 
1307
        sorted together, and grandchildren are in the same order as the
 
1308
        children appear. But all grandchildren come after all children.
 
1309
 
 
1310
        :param path1: first path
 
1311
        :param path2: the second path
 
1312
        :return: negative number if ``path1`` comes first,
 
1313
            0 if paths are equal
 
1314
            and a positive number if ``path2`` sorts first
 
1315
        """
 
1316
        # Shortcut this special case
 
1317
        if path1 == path2:
 
1318
            return 0
 
1319
        # This is stolen from _dirstate_helpers_py.py, only switching it to
 
1320
        # Unicode objects. Consider using encode_utf8() and then using the
 
1321
        # optimized versions, or maybe writing optimized unicode versions.
 
1322
        if not isinstance(path1, unicode):
 
1323
            raise TypeError("'path1' must be a unicode string, not %s: %r"
 
1324
                            % (type(path1), path1))
 
1325
        if not isinstance(path2, unicode):
 
1326
            raise TypeError("'path2' must be a unicode string, not %s: %r"
 
1327
                            % (type(path2), path2))
 
1328
        return cmp(MultiWalker._path_to_key(path1),
 
1329
                   MultiWalker._path_to_key(path2))
 
1330
 
 
1331
    @staticmethod
 
1332
    def _path_to_key(path):
 
1333
        dirname, basename = osutils.split(path)
 
1334
        return (dirname.split(u'/'), basename)
 
1335
 
 
1336
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
 
1337
        """Lookup an inventory entry by file_id.
 
1338
 
 
1339
        This is called when an entry is missing in the normal order.
 
1340
        Generally this is because a file was either renamed, or it was
 
1341
        deleted/added. If the entry was found in the inventory and not in
 
1342
        extra_entries, it will be added to self._out_of_order_processed
 
1343
 
 
1344
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
 
1345
            should be filled with entries that were found before they were
 
1346
            used. If file_id is present, it will be removed from the
 
1347
            dictionary.
 
1348
        :param other_tree: The Tree to search, in case we didn't find the entry
 
1349
            yet.
 
1350
        :param file_id: The file_id to look for
 
1351
        :return: (path, ie) if found or (None, None) if not present.
 
1352
        """
 
1353
        if file_id in extra_entries:
 
1354
            return extra_entries.pop(file_id)
 
1355
        # TODO: Is id2path better as the first call, or is
 
1356
        #       inventory[file_id] better as a first check?
 
1357
        try:
 
1358
            cur_path = other_tree.id2path(file_id)
 
1359
        except errors.NoSuchId:
 
1360
            cur_path = None
 
1361
        if cur_path is None:
 
1362
            return (None, None)
 
1363
        else:
 
1364
            self._out_of_order_processed.add(file_id)
 
1365
            cur_ie = other_tree.inventory[file_id]
 
1366
            return (cur_path, cur_ie)
 
1367
 
 
1368
    def iter_all(self):
 
1369
        """Match up the values in the different trees."""
 
1370
        for result in self._walk_master_tree():
 
1371
            yield result
 
1372
        self._finish_others()
 
1373
        for result in self._walk_others():
 
1374
            yield result
 
1375
 
 
1376
    def _walk_master_tree(self):
 
1377
        """First pass, walk all trees in lock-step.
 
1378
 
 
1379
        When we are done, all nodes in the master_tree will have been
 
1380
        processed. _other_walkers, _other_entries, and _others_extra will be
 
1381
        set on 'self' for future processing.
 
1382
        """
 
1383
        # This iterator has the most "inlining" done, because it tends to touch
 
1384
        # every file in the tree, while the others only hit nodes that don't
 
1385
        # match.
 
1386
        master_iterator = self._master_tree.iter_entries_by_dir()
 
1387
 
 
1388
        other_walkers = [other.iter_entries_by_dir()
 
1389
                         for other in self._other_trees]
 
1390
        other_entries = [self._step_one(walker) for walker in other_walkers]
 
1391
        # Track extra nodes in the other trees
 
1392
        others_extra = [{} for i in xrange(len(self._other_trees))]
 
1393
 
 
1394
        master_has_more = True
 
1395
        step_one = self._step_one
 
1396
        lookup_by_file_id = self._lookup_by_file_id
 
1397
        out_of_order_processed = self._out_of_order_processed
 
1398
 
 
1399
        while master_has_more:
 
1400
            (master_has_more, path, master_ie) = step_one(master_iterator)
 
1401
            if not master_has_more:
 
1402
                break
 
1403
 
 
1404
            file_id = master_ie.file_id
 
1405
            other_values = []
 
1406
            other_values_append = other_values.append
 
1407
            next_other_entries = []
 
1408
            next_other_entries_append = next_other_entries.append
 
1409
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
 
1410
                if not other_has_more:
 
1411
                    other_values_append(lookup_by_file_id(
 
1412
                        others_extra[idx], self._other_trees[idx], file_id))
 
1413
                    next_other_entries_append((False, None, None))
 
1414
                elif file_id == other_ie.file_id:
 
1415
                    # This is the critical code path, as most of the entries
 
1416
                    # should match between most trees.
 
1417
                    other_values_append((other_path, other_ie))
 
1418
                    next_other_entries_append(step_one(other_walkers[idx]))
 
1419
                else:
 
1420
                    # This walker did not match, step it until it either
 
1421
                    # matches, or we know we are past the current walker.
 
1422
                    other_walker = other_walkers[idx]
 
1423
                    other_extra = others_extra[idx]
 
1424
                    while (other_has_more and
 
1425
                           self._cmp_path_by_dirblock(other_path, path) < 0):
 
1426
                        other_file_id = other_ie.file_id
 
1427
                        if other_file_id not in out_of_order_processed:
 
1428
                            other_extra[other_file_id] = (other_path, other_ie)
 
1429
                        other_has_more, other_path, other_ie = \
 
1430
                            step_one(other_walker)
 
1431
                    if other_has_more and other_ie.file_id == file_id:
 
1432
                        # We ended up walking to this point, match and step
 
1433
                        # again
 
1434
                        other_values_append((other_path, other_ie))
 
1435
                        other_has_more, other_path, other_ie = \
 
1436
                            step_one(other_walker)
 
1437
                    else:
 
1438
                        # This record isn't in the normal order, see if it
 
1439
                        # exists at all.
 
1440
                        other_values_append(lookup_by_file_id(
 
1441
                            other_extra, self._other_trees[idx], file_id))
 
1442
                    next_other_entries_append((other_has_more, other_path,
 
1443
                                               other_ie))
 
1444
            other_entries = next_other_entries
 
1445
 
 
1446
            # We've matched all the walkers, yield this datapoint
 
1447
            yield path, file_id, master_ie, other_values
 
1448
        self._other_walkers = other_walkers
 
1449
        self._other_entries = other_entries
 
1450
        self._others_extra = others_extra
 
1451
 
 
1452
    def _finish_others(self):
 
1453
        """Finish walking the other iterators, so we get all entries."""
 
1454
        for idx, info in enumerate(self._other_entries):
 
1455
            other_extra = self._others_extra[idx]
 
1456
            (other_has_more, other_path, other_ie) = info
 
1457
            while other_has_more:
 
1458
                other_file_id = other_ie.file_id
 
1459
                if other_file_id not in self._out_of_order_processed:
 
1460
                    other_extra[other_file_id] = (other_path, other_ie)
 
1461
                other_has_more, other_path, other_ie = \
 
1462
                    self._step_one(self._other_walkers[idx])
 
1463
        del self._other_entries
 
1464
 
 
1465
    def _walk_others(self):
 
1466
        """Finish up by walking all the 'deferred' nodes."""
 
1467
        # TODO: One alternative would be to grab all possible unprocessed
 
1468
        #       file_ids, and then sort by path, and then yield them. That
 
1469
        #       might ensure better ordering, in case a caller strictly
 
1470
        #       requires parents before children.
 
1471
        for idx, other_extra in enumerate(self._others_extra):
 
1472
            others = sorted(other_extra.itervalues(),
 
1473
                            key=lambda x: self._path_to_key(x[0]))
 
1474
            for other_path, other_ie in others:
 
1475
                file_id = other_ie.file_id
 
1476
                # We don't need to check out_of_order_processed here, because
 
1477
                # the lookup_by_file_id will be removing anything processed
 
1478
                # from the extras cache
 
1479
                other_extra.pop(file_id)
 
1480
                other_values = [(None, None) for i in xrange(idx)]
 
1481
                other_values.append((other_path, other_ie))
 
1482
                for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
 
1483
                    alt_idx = alt_idx + idx + 1
 
1484
                    alt_extra = self._others_extra[alt_idx]
 
1485
                    alt_tree = self._other_trees[alt_idx]
 
1486
                    other_values.append(self._lookup_by_file_id(
 
1487
                                            alt_extra, alt_tree, file_id))
 
1488
                yield other_path, file_id, None, other_values