~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

  • Committer: INADA Naoki
  • Date: 2011-05-18 06:27:34 UTC
  • mfrom: (5887 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5894.
  • Revision ID: songofacandy@gmail.com-20110518062734-1ilhll0rrqyyp8um
merge from lp:bzr and resolve conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2009 Canonical Ltd
 
1
# Copyright (C) 2005-2011 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
18
18
"""
19
19
 
20
20
import os
21
 
from collections import deque
22
 
 
23
 
import bzrlib
 
21
 
 
22
from bzrlib.lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import collections
 
25
 
24
26
from bzrlib import (
25
27
    conflicts as _mod_conflicts,
26
28
    debug,
27
29
    delta,
 
30
    errors,
28
31
    filters,
 
32
    inventory,
29
33
    osutils,
30
34
    revision as _mod_revision,
31
35
    rules,
 
36
    trace,
32
37
    )
 
38
""")
 
39
 
33
40
from bzrlib.decorators import needs_read_lock
34
 
from bzrlib.errors import BzrError, NoSuchId
35
 
from bzrlib import errors
36
 
from bzrlib.inventory import InventoryFile
37
41
from bzrlib.inter import InterObject
38
 
from bzrlib.osutils import fingerprint_file
39
 
import bzrlib.revision
40
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
41
 
from bzrlib.trace import note
 
42
from bzrlib.symbol_versioning import (
 
43
    deprecated_in,
 
44
    deprecated_method,
 
45
    )
42
46
 
43
47
 
44
48
class Tree(object):
50
54
 
51
55
    * `RevisionTree` is a tree as recorded at some point in the past.
52
56
 
53
 
    Trees contain an `Inventory` object, and also know how to retrieve
54
 
    file texts mentioned in the inventory, either from a working
55
 
    directory or from a store.
56
 
 
57
 
    It is possible for trees to contain files that are not described
58
 
    in their inventory or vice versa; for this use `filenames()`.
59
 
 
60
57
    Trees can be compared, etc, regardless of whether they are working
61
58
    trees or versioned trees.
62
59
    """
98
95
    def iter_changes(self, from_tree, include_unchanged=False,
99
96
                     specific_files=None, pb=None, extra_trees=None,
100
97
                     require_versioned=True, want_unversioned=False):
 
98
        """See InterTree.iter_changes"""
101
99
        intertree = InterTree.get(from_tree, self)
102
100
        return intertree.iter_changes(include_unchanged, specific_files, pb,
103
101
            extra_trees, require_versioned, want_unversioned=want_unversioned)
127
125
        raise NotImplementedError(self.has_filename)
128
126
 
129
127
    def has_id(self, file_id):
130
 
        return self.inventory.has_id(file_id)
 
128
        raise NotImplementedError(self.has_id)
131
129
 
132
130
    def __contains__(self, file_id):
133
131
        return self.has_id(file_id)
134
132
 
135
133
    def has_or_had_id(self, file_id):
136
 
        return self.inventory.has_id(file_id)
 
134
        raise NotImplementedError(self.has_or_had_id)
137
135
 
138
136
    def is_ignored(self, filename):
139
137
        """Check whether the filename is ignored by this tree.
143
141
        """
144
142
        return False
145
143
 
146
 
    def __iter__(self):
147
 
        return iter(self.inventory)
148
 
 
149
144
    def all_file_ids(self):
150
145
        """Iterate through all file ids, including ids for missing files."""
151
 
        return set(self.inventory)
 
146
        raise NotImplementedError(self.all_file_ids)
152
147
 
153
148
    def id2path(self, file_id):
154
149
        """Return the path for a file id.
155
150
 
156
151
        :raises NoSuchId:
157
152
        """
158
 
        return self.inventory.id2path(file_id)
159
 
 
160
 
    def is_control_filename(self, filename):
161
 
        """True if filename is the name of a control file in this tree.
162
 
 
163
 
        :param filename: A filename within the tree. This is a relative path
164
 
        from the root of this tree.
165
 
 
166
 
        This is true IF and ONLY IF the filename is part of the meta data
167
 
        that bzr controls in this tree. I.E. a random .bzr directory placed
168
 
        on disk will not be a control file for this tree.
169
 
        """
170
 
        return self.bzrdir.is_control_filename(filename)
171
 
 
172
 
    @needs_read_lock
173
 
    def iter_entries_by_dir(self, specific_file_ids=None):
 
153
        raise NotImplementedError(self.id2path)
 
154
 
 
155
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
174
156
        """Walk the tree in 'by_dir' order.
175
157
 
176
158
        This will yield each entry in the tree as a (path, entry) tuple.
193
175
 
194
176
        The yield order (ignoring root) would be::
195
177
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
196
 
        """
197
 
        return self.inventory.iter_entries_by_dir(
198
 
            specific_file_ids=specific_file_ids)
 
178
 
 
179
        :param yield_parents: If True, yield the parents from the root leading
 
180
            down to specific_file_ids that have been requested. This has no
 
181
            impact if specific_file_ids is None.
 
182
        """
 
183
        raise NotImplementedError(self.iter_entries_by_dir)
 
184
 
 
185
    def list_files(self, include_root=False, from_dir=None, recursive=True):
 
186
        """List all files in this tree.
 
187
 
 
188
        :param include_root: Whether to include the entry for the tree root
 
189
        :param from_dir: Directory under which to list files
 
190
        :param recursive: Whether to list files recursively
 
191
        :return: iterator over tuples of (path, versioned, kind, file_id,
 
192
            inventory entry)
 
193
        """
 
194
        raise NotImplementedError(self.list_files)
199
195
 
200
196
    def iter_references(self):
201
197
        if self.supports_tree_reference():
218
214
    def path_content_summary(self, path):
219
215
        """Get a summary of the information about path.
220
216
 
 
217
        All the attributes returned are for the canonical form, not the
 
218
        convenient form (if content filters are in use.)
 
219
 
221
220
        :param path: A relative path within the tree.
222
221
        :return: A tuple containing kind, size, exec, sha1-or-link.
223
222
            Kind is always present (see tree.kind()).
224
 
            size is present if kind is file, None otherwise.
 
223
            size is present if kind is file and the size of the 
 
224
                canonical form can be cheaply determined, None otherwise.
225
225
            exec is None unless kind is file and the platform supports the 'x'
226
226
                bit.
227
227
            sha1-or-link is the link target if kind is symlink, or the sha1 if
248
248
    def _file_size(self, entry, stat_value):
249
249
        raise NotImplementedError(self._file_size)
250
250
 
251
 
    def _get_inventory(self):
252
 
        return self._inventory
253
 
 
254
251
    def get_file(self, file_id, path=None):
255
252
        """Return a file object for the file file_id in the tree.
256
253
 
297
294
        """
298
295
        return osutils.split_lines(self.get_file_text(file_id, path))
299
296
 
 
297
    def get_file_sha1(self, file_id, path=None):
 
298
        """Return the SHA1 file for a file.
 
299
 
 
300
        :param file_id: The handle for this file.
 
301
        :param path: The path that this file can be found at.
 
302
            These must point to the same object.
 
303
        """
 
304
        raise NotImplementedError(self.get_file_sha1)
 
305
 
300
306
    def get_file_mtime(self, file_id, path=None):
301
307
        """Return the modification time for a file.
302
308
 
316
322
        raise NotImplementedError(self.get_file_size)
317
323
 
318
324
    def get_file_by_path(self, path):
319
 
        return self.get_file(self._inventory.path2id(path), path)
 
325
        raise NotImplementedError(self.get_file_by_path)
 
326
 
 
327
    def is_executable(self, file_id, path=None):
 
328
        """Check if a file is executable.
 
329
 
 
330
        :param file_id: The handle for this file.
 
331
        :param path: The path that this file can be found at.
 
332
            These must point to the same object.
 
333
        """
 
334
        raise NotImplementedError(self.is_executable)
320
335
 
321
336
    def iter_files_bytes(self, desired_files):
322
337
        """Iterate through file contents.
344
359
            cur_file = (self.get_file_text(file_id),)
345
360
            yield identifier, cur_file
346
361
 
347
 
    def get_symlink_target(self, file_id):
 
362
    def get_symlink_target(self, file_id, path=None):
348
363
        """Get the target for a given file_id.
349
364
 
350
365
        It is assumed that the caller already knows that file_id is referencing
351
366
        a symlink.
352
367
        :param file_id: Handle for the symlink entry.
 
368
        :param path: The path of the file.
 
369
        If both file_id and path are supplied, an implementation may use
 
370
        either one.
353
371
        :return: The path the symlink points to.
354
372
        """
355
373
        raise NotImplementedError(self.get_symlink_target)
356
374
 
357
 
    def get_canonical_inventory_paths(self, paths):
358
 
        """Like get_canonical_inventory_path() but works on multiple items.
359
 
 
360
 
        :param paths: A sequence of paths relative to the root of the tree.
361
 
        :return: A list of paths, with each item the corresponding input path
362
 
        adjusted to account for existing elements that match case
363
 
        insensitively.
364
 
        """
365
 
        return list(self._yield_canonical_inventory_paths(paths))
366
 
 
367
 
    def get_canonical_inventory_path(self, path):
368
 
        """Returns the first inventory item that case-insensitively matches path.
369
 
 
370
 
        If a path matches exactly, it is returned. If no path matches exactly
371
 
        but more than one path matches case-insensitively, it is implementation
372
 
        defined which is returned.
373
 
 
374
 
        If no path matches case-insensitively, the input path is returned, but
375
 
        with as many path entries that do exist changed to their canonical
376
 
        form.
377
 
 
378
 
        If you need to resolve many names from the same tree, you should
379
 
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
380
 
 
381
 
        :param path: A paths relative to the root of the tree.
382
 
        :return: The input path adjusted to account for existing elements
383
 
        that match case insensitively.
384
 
        """
385
 
        return self._yield_canonical_inventory_paths([path]).next()
386
 
 
387
 
    def _yield_canonical_inventory_paths(self, paths):
388
 
        for path in paths:
389
 
            # First, if the path as specified exists exactly, just use it.
390
 
            if self.path2id(path) is not None:
391
 
                yield path
392
 
                continue
393
 
            # go walkin...
394
 
            cur_id = self.get_root_id()
395
 
            cur_path = ''
396
 
            bit_iter = iter(path.split("/"))
397
 
            for elt in bit_iter:
398
 
                lelt = elt.lower()
399
 
                for child in self.iter_children(cur_id):
400
 
                    try:
401
 
                        child_base = os.path.basename(self.id2path(child))
402
 
                        if child_base.lower() == lelt:
403
 
                            cur_id = child
404
 
                            cur_path = osutils.pathjoin(cur_path, child_base)
405
 
                            break
406
 
                    except NoSuchId:
407
 
                        # before a change is committed we can see this error...
408
 
                        continue
409
 
                else:
410
 
                    # got to the end of this directory and no entries matched.
411
 
                    # Return what matched so far, plus the rest as specified.
412
 
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
413
 
                    break
414
 
            yield cur_path
415
 
        # all done.
416
 
 
417
375
    def get_root_id(self):
418
376
        """Return the file_id for the root of this tree."""
419
377
        raise NotImplementedError(self.get_root_id)
477
435
            except errors.NoSuchRevisionInTree:
478
436
                yield self.repository.revision_tree(revision_id)
479
437
 
480
 
    @staticmethod
481
 
    def _file_revision(revision_tree, file_id):
482
 
        """Determine the revision associated with a file in a given tree."""
483
 
        revision_tree.lock_read()
484
 
        try:
485
 
            return revision_tree.inventory[file_id].revision
486
 
        finally:
487
 
            revision_tree.unlock()
488
 
 
489
438
    def _get_file_revision(self, file_id, vf, tree_revision):
490
439
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
491
440
 
492
441
        if getattr(self, '_repository', None) is None:
493
442
            last_revision = tree_revision
494
 
            parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
 
443
            parent_keys = [(file_id, t.get_file_revision(file_id)) for t in
495
444
                self._iter_parent_trees()]
496
445
            vf.add_lines((file_id, last_revision), parent_keys,
497
 
                         self.get_file(file_id).readlines())
 
446
                         self.get_file_lines(file_id))
498
447
            repo = self.branch.repository
499
448
            base_vf = repo.texts
500
449
        else:
501
 
            last_revision = self._file_revision(self, file_id)
 
450
            last_revision = self.get_file_revision(file_id)
502
451
            base_vf = self._repository.texts
503
452
        if base_vf not in vf.fallback_versionedfiles:
504
453
            vf.fallback_versionedfiles.append(base_vf)
505
454
        return last_revision
506
455
 
507
 
    inventory = property(_get_inventory,
508
 
                         doc="Inventory of this Tree")
509
 
 
510
456
    def _check_retrieved(self, ie, f):
511
457
        if not __debug__:
512
458
            return
513
 
        fp = fingerprint_file(f)
 
459
        fp = osutils.fingerprint_file(f)
514
460
        f.seek(0)
515
461
 
516
462
        if ie.text_size is not None:
517
463
            if ie.text_size != fp['size']:
518
 
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
 
464
                raise errors.BzrError(
 
465
                        "mismatched size for file %r in %r" %
 
466
                        (ie.file_id, self._store),
519
467
                        ["inventory expects %d bytes" % ie.text_size,
520
468
                         "file is actually %d bytes" % fp['size'],
521
469
                         "store is probably damaged/corrupt"])
522
470
 
523
471
        if ie.text_sha1 != fp['sha1']:
524
 
            raise BzrError("wrong SHA-1 for file %r in %r" % (ie.file_id, self._store),
 
472
            raise errors.BzrError("wrong SHA-1 for file %r in %r" %
 
473
                    (ie.file_id, self._store),
525
474
                    ["inventory expects %s" % ie.text_sha1,
526
475
                     "file is actually %s" % fp['sha1'],
527
476
                     "store is probably damaged/corrupt"])
528
477
 
529
 
    @needs_read_lock
530
478
    def path2id(self, path):
531
479
        """Return the id for path in this tree."""
532
 
        return self._inventory.path2id(path)
 
480
        raise NotImplementedError(self.path2id)
533
481
 
534
482
    def paths2ids(self, paths, trees=[], require_versioned=True):
535
483
        """Return all the ids that can be reached by walking from paths.
556
504
            yield child.file_id
557
505
 
558
506
    def lock_read(self):
 
507
        """Lock this tree for multiple read only operations.
 
508
        
 
509
        :return: A bzrlib.lock.LogicalLockResult.
 
510
        """
559
511
        pass
560
512
 
561
513
    def revision_tree(self, revision_id):
588
540
 
589
541
        :return: set of paths.
590
542
        """
591
 
        # NB: we specifically *don't* call self.has_filename, because for
592
 
        # WorkingTrees that can indicate files that exist on disk but that
593
 
        # are not versioned.
594
 
        pred = self.inventory.has_filename
595
 
        return set((p for p in paths if not pred(p)))
 
543
        raise NotImplementedError(self.filter_unversioned_files)
596
544
 
597
545
    def walkdirs(self, prefix=""):
598
546
        """Walk the contents of this tree from path down.
650
598
        prefs = self.iter_search_rules([path], filter_pref_names).next()
651
599
        stk = filters._get_filter_stack_for(prefs)
652
600
        if 'filters' in debug.debug_flags:
653
 
            note("*** %s content-filter: %s => %r" % (path,prefs,stk))
 
601
            trace.note("*** %s content-filter: %s => %r" % (path,prefs,stk))
654
602
        return stk
655
603
 
656
604
    def _content_filter_stack_provider(self):
689
637
                for path in path_names:
690
638
                    yield searcher.get_items(path)
691
639
 
692
 
    @needs_read_lock
693
640
    def _get_rules_searcher(self, default_searcher):
694
641
        """Get the RulesSearcher for this tree given the default one."""
695
642
        searcher = default_searcher
696
643
        return searcher
697
644
 
698
645
 
 
646
class InventoryTree(Tree):
 
647
    """A tree that relies on an inventory for its metadata.
 
648
 
 
649
    Trees contain an `Inventory` object, and also know how to retrieve
 
650
    file texts mentioned in the inventory, either from a working
 
651
    directory or from a store.
 
652
 
 
653
    It is possible for trees to contain files that are not described
 
654
    in their inventory or vice versa; for this use `filenames()`.
 
655
 
 
656
    Subclasses should set the _inventory attribute, which is considered
 
657
    private to external API users.
 
658
    """
 
659
 
 
660
    def get_canonical_inventory_paths(self, paths):
 
661
        """Like get_canonical_inventory_path() but works on multiple items.
 
662
 
 
663
        :param paths: A sequence of paths relative to the root of the tree.
 
664
        :return: A list of paths, with each item the corresponding input path
 
665
        adjusted to account for existing elements that match case
 
666
        insensitively.
 
667
        """
 
668
        return list(self._yield_canonical_inventory_paths(paths))
 
669
 
 
670
    def get_canonical_inventory_path(self, path):
 
671
        """Returns the first inventory item that case-insensitively matches path.
 
672
 
 
673
        If a path matches exactly, it is returned. If no path matches exactly
 
674
        but more than one path matches case-insensitively, it is implementation
 
675
        defined which is returned.
 
676
 
 
677
        If no path matches case-insensitively, the input path is returned, but
 
678
        with as many path entries that do exist changed to their canonical
 
679
        form.
 
680
 
 
681
        If you need to resolve many names from the same tree, you should
 
682
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
683
 
 
684
        :param path: A paths relative to the root of the tree.
 
685
        :return: The input path adjusted to account for existing elements
 
686
        that match case insensitively.
 
687
        """
 
688
        return self._yield_canonical_inventory_paths([path]).next()
 
689
 
 
690
    def _yield_canonical_inventory_paths(self, paths):
 
691
        for path in paths:
 
692
            # First, if the path as specified exists exactly, just use it.
 
693
            if self.path2id(path) is not None:
 
694
                yield path
 
695
                continue
 
696
            # go walkin...
 
697
            cur_id = self.get_root_id()
 
698
            cur_path = ''
 
699
            bit_iter = iter(path.split("/"))
 
700
            for elt in bit_iter:
 
701
                lelt = elt.lower()
 
702
                new_path = None
 
703
                for child in self.iter_children(cur_id):
 
704
                    try:
 
705
                        # XXX: it seem like if the child is known to be in the
 
706
                        # tree, we shouldn't need to go from its id back to
 
707
                        # its path -- mbp 2010-02-11
 
708
                        #
 
709
                        # XXX: it seems like we could be more efficient
 
710
                        # by just directly looking up the original name and
 
711
                        # only then searching all children; also by not
 
712
                        # chopping paths so much. -- mbp 2010-02-11
 
713
                        child_base = os.path.basename(self.id2path(child))
 
714
                        if (child_base == elt):
 
715
                            # if we found an exact match, we can stop now; if
 
716
                            # we found an approximate match we need to keep
 
717
                            # searching because there might be an exact match
 
718
                            # later.  
 
719
                            cur_id = child
 
720
                            new_path = osutils.pathjoin(cur_path, child_base)
 
721
                            break
 
722
                        elif child_base.lower() == lelt:
 
723
                            cur_id = child
 
724
                            new_path = osutils.pathjoin(cur_path, child_base)
 
725
                    except errors.NoSuchId:
 
726
                        # before a change is committed we can see this error...
 
727
                        continue
 
728
                if new_path:
 
729
                    cur_path = new_path
 
730
                else:
 
731
                    # got to the end of this directory and no entries matched.
 
732
                    # Return what matched so far, plus the rest as specified.
 
733
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
734
                    break
 
735
            yield cur_path
 
736
        # all done.
 
737
 
 
738
    def _get_inventory(self):
 
739
        return self._inventory
 
740
 
 
741
    inventory = property(_get_inventory,
 
742
                         doc="Inventory of this Tree")
 
743
 
 
744
    @needs_read_lock
 
745
    def path2id(self, path):
 
746
        """Return the id for path in this tree."""
 
747
        return self._inventory.path2id(path)
 
748
 
 
749
    def id2path(self, file_id):
 
750
        """Return the path for a file id.
 
751
 
 
752
        :raises NoSuchId:
 
753
        """
 
754
        return self.inventory.id2path(file_id)
 
755
 
 
756
    def has_id(self, file_id):
 
757
        return self.inventory.has_id(file_id)
 
758
 
 
759
    def has_or_had_id(self, file_id):
 
760
        return self.inventory.has_id(file_id)
 
761
 
 
762
    def all_file_ids(self):
 
763
        return set(self.inventory)
 
764
 
 
765
    @deprecated_method(deprecated_in((2, 4, 0)))
 
766
    def __iter__(self):
 
767
        return iter(self.inventory)
 
768
 
 
769
    def filter_unversioned_files(self, paths):
 
770
        """Filter out paths that are versioned.
 
771
 
 
772
        :return: set of paths.
 
773
        """
 
774
        # NB: we specifically *don't* call self.has_filename, because for
 
775
        # WorkingTrees that can indicate files that exist on disk but that
 
776
        # are not versioned.
 
777
        pred = self.inventory.has_filename
 
778
        return set((p for p in paths if not pred(p)))
 
779
 
 
780
    @needs_read_lock
 
781
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
 
782
        """Walk the tree in 'by_dir' order.
 
783
 
 
784
        This will yield each entry in the tree as a (path, entry) tuple.
 
785
        The order that they are yielded is:
 
786
 
 
787
        See Tree.iter_entries_by_dir for details.
 
788
 
 
789
        :param yield_parents: If True, yield the parents from the root leading
 
790
            down to specific_file_ids that have been requested. This has no
 
791
            impact if specific_file_ids is None.
 
792
        """
 
793
        return self.inventory.iter_entries_by_dir(
 
794
            specific_file_ids=specific_file_ids, yield_parents=yield_parents)
 
795
 
 
796
    def get_file_by_path(self, path):
 
797
        return self.get_file(self._inventory.path2id(path), path)
 
798
 
 
799
 
699
800
######################################################################
700
801
# diff
701
802
 
749
850
    return 'wtf?'
750
851
 
751
852
 
752
 
@deprecated_function(deprecated_in((1, 9, 0)))
753
 
def find_renames(old_inv, new_inv):
754
 
    for file_id in old_inv:
755
 
        if file_id not in new_inv:
756
 
            continue
757
 
        old_name = old_inv.id2path(file_id)
758
 
        new_name = new_inv.id2path(file_id)
759
 
        if old_name != new_name:
760
 
            yield (old_name, new_name)
761
 
 
762
 
 
763
853
def find_ids_across_trees(filenames, trees, require_versioned=True):
764
854
    """Find the ids corresponding to specified filenames.
765
855
 
844
934
    will pass through to InterTree as appropriate.
845
935
    """
846
936
 
 
937
    # Formats that will be used to test this InterTree. If both are
 
938
    # None, this InterTree will not be tested (e.g. because a complex
 
939
    # setup is required)
 
940
    _matching_from_tree_format = None
 
941
    _matching_to_tree_format = None
 
942
 
847
943
    _optimisers = []
848
944
 
 
945
    @classmethod
 
946
    def is_compatible(kls, source, target):
 
947
        # The default implementation is naive and uses the public API, so
 
948
        # it works for all trees.
 
949
        return True
 
950
 
 
951
    def _changes_from_entries(self, source_entry, target_entry,
 
952
        source_path=None, target_path=None):
 
953
        """Generate a iter_changes tuple between source_entry and target_entry.
 
954
 
 
955
        :param source_entry: An inventory entry from self.source, or None.
 
956
        :param target_entry: An inventory entry from self.target, or None.
 
957
        :param source_path: The path of source_entry, if known. If not known
 
958
            it will be looked up.
 
959
        :param target_path: The path of target_entry, if known. If not known
 
960
            it will be looked up.
 
961
        :return: A tuple, item 0 of which is an iter_changes result tuple, and
 
962
            item 1 is True if there are any changes in the result tuple.
 
963
        """
 
964
        if source_entry is None:
 
965
            if target_entry is None:
 
966
                return None
 
967
            file_id = target_entry.file_id
 
968
        else:
 
969
            file_id = source_entry.file_id
 
970
        if source_entry is not None:
 
971
            source_versioned = True
 
972
            source_name = source_entry.name
 
973
            source_parent = source_entry.parent_id
 
974
            if source_path is None:
 
975
                source_path = self.source.id2path(file_id)
 
976
            source_kind, source_executable, source_stat = \
 
977
                self.source._comparison_data(source_entry, source_path)
 
978
        else:
 
979
            source_versioned = False
 
980
            source_name = None
 
981
            source_parent = None
 
982
            source_kind = None
 
983
            source_executable = None
 
984
        if target_entry is not None:
 
985
            target_versioned = True
 
986
            target_name = target_entry.name
 
987
            target_parent = target_entry.parent_id
 
988
            if target_path is None:
 
989
                target_path = self.target.id2path(file_id)
 
990
            target_kind, target_executable, target_stat = \
 
991
                self.target._comparison_data(target_entry, target_path)
 
992
        else:
 
993
            target_versioned = False
 
994
            target_name = None
 
995
            target_parent = None
 
996
            target_kind = None
 
997
            target_executable = None
 
998
        versioned = (source_versioned, target_versioned)
 
999
        kind = (source_kind, target_kind)
 
1000
        changed_content = False
 
1001
        if source_kind != target_kind:
 
1002
            changed_content = True
 
1003
        elif source_kind == 'file':
 
1004
            if (self.source.get_file_sha1(file_id, source_path, source_stat) !=
 
1005
                self.target.get_file_sha1(file_id, target_path, target_stat)):
 
1006
                changed_content = True
 
1007
        elif source_kind == 'symlink':
 
1008
            if (self.source.get_symlink_target(file_id) !=
 
1009
                self.target.get_symlink_target(file_id)):
 
1010
                changed_content = True
 
1011
            # XXX: Yes, the indentation below is wrong. But fixing it broke
 
1012
            # test_merge.TestMergerEntriesLCAOnDisk.
 
1013
            # test_nested_tree_subtree_renamed_and_modified. We'll wait for
 
1014
            # the fix from bzr.dev -- vila 2009026
 
1015
            elif source_kind == 'tree-reference':
 
1016
                if (self.source.get_reference_revision(file_id, source_path)
 
1017
                    != self.target.get_reference_revision(file_id, target_path)):
 
1018
                    changed_content = True
 
1019
        parent = (source_parent, target_parent)
 
1020
        name = (source_name, target_name)
 
1021
        executable = (source_executable, target_executable)
 
1022
        if (changed_content is not False or versioned[0] != versioned[1]
 
1023
            or parent[0] != parent[1] or name[0] != name[1] or
 
1024
            executable[0] != executable[1]):
 
1025
            changes = True
 
1026
        else:
 
1027
            changes = False
 
1028
        return (file_id, (source_path, target_path), changed_content,
 
1029
                versioned, parent, name, kind, executable), changes
 
1030
 
849
1031
    @needs_read_lock
850
1032
    def compare(self, want_unchanged=False, specific_files=None,
851
1033
        extra_trees=None, require_versioned=False, include_root=False,
866
1048
            a PathsNotVersionedError will be thrown.
867
1049
        :param want_unversioned: Scan for unversioned paths.
868
1050
        """
869
 
        # NB: show_status depends on being able to pass in non-versioned files
870
 
        # and report them as unknown
871
1051
        trees = (self.source,)
872
1052
        if extra_trees is not None:
873
1053
            trees = trees + tuple(extra_trees)
878
1058
            # All files are unversioned, so just return an empty delta
879
1059
            # _compare_trees would think we want a complete delta
880
1060
            result = delta.TreeDelta()
881
 
            fake_entry = InventoryFile('unused', 'unused', 'unused')
 
1061
            fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
882
1062
            result.unversioned = [(path, None,
883
1063
                self.target._comparison_data(fake_entry, path)[0]) for path in
884
1064
                specific_files]
914
1094
        :param require_versioned: Raise errors.PathsNotVersionedError if a
915
1095
            path in the specific_files list is not versioned in one of
916
1096
            source, target or extra_trees.
 
1097
        :param specific_files: An optional list of file paths to restrict the
 
1098
            comparison to. When mapping filenames to ids, all matches in all
 
1099
            trees (including optional extra_trees) are used, and all children
 
1100
            of matched directories are included. The parents in the target tree
 
1101
            of the specific files up to and including the root of the tree are
 
1102
            always evaluated for changes too.
917
1103
        :param want_unversioned: Should unversioned files be returned in the
918
1104
            output. An unversioned file is defined as one with (False, False)
919
1105
            for the versioned pair.
921
1107
        lookup_trees = [self.source]
922
1108
        if extra_trees:
923
1109
             lookup_trees.extend(extra_trees)
 
1110
        # The ids of items we need to examine to insure delta consistency.
 
1111
        precise_file_ids = set()
 
1112
        changed_file_ids = []
924
1113
        if specific_files == []:
925
1114
            specific_file_ids = []
926
1115
        else:
927
1116
            specific_file_ids = self.target.paths2ids(specific_files,
928
1117
                lookup_trees, require_versioned=require_versioned)
 
1118
        if specific_files is not None:
 
1119
            # reparented or added entries must have their parents included
 
1120
            # so that valid deltas can be created. The seen_parents set
 
1121
            # tracks the parents that we need to have.
 
1122
            # The seen_dirs set tracks directory entries we've yielded.
 
1123
            # After outputting version object in to_entries we set difference
 
1124
            # the two seen sets and start checking parents.
 
1125
            seen_parents = set()
 
1126
            seen_dirs = set()
929
1127
        if want_unversioned:
930
1128
            all_unversioned = sorted([(p.split('/'), p) for p in
931
1129
                                     self.target.extras()
932
1130
                if specific_files is None or
933
1131
                    osutils.is_inside_any(specific_files, p)])
934
 
            all_unversioned = deque(all_unversioned)
 
1132
            all_unversioned = collections.deque(all_unversioned)
935
1133
        else:
936
 
            all_unversioned = deque()
 
1134
            all_unversioned = collections.deque()
937
1135
        to_paths = {}
938
1136
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
939
1137
            specific_file_ids=specific_file_ids))
945
1143
        # the unversioned path lookup only occurs on real trees - where there
946
1144
        # can be extras. So the fake_entry is solely used to look up
947
1145
        # executable it values when execute is not supported.
948
 
        fake_entry = InventoryFile('unused', 'unused', 'unused')
949
 
        for to_path, to_entry in to_entries_by_dir:
950
 
            while all_unversioned and all_unversioned[0][0] < to_path.split('/'):
 
1146
        fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
 
1147
        for target_path, target_entry in to_entries_by_dir:
 
1148
            while (all_unversioned and
 
1149
                all_unversioned[0][0] < target_path.split('/')):
951
1150
                unversioned_path = all_unversioned.popleft()
952
 
                to_kind, to_executable, to_stat = \
 
1151
                target_kind, target_executable, target_stat = \
953
1152
                    self.target._comparison_data(fake_entry, unversioned_path[1])
954
1153
                yield (None, (None, unversioned_path[1]), True, (False, False),
955
1154
                    (None, None),
956
1155
                    (None, unversioned_path[0][-1]),
957
 
                    (None, to_kind),
958
 
                    (None, to_executable))
959
 
            file_id = to_entry.file_id
960
 
            to_paths[file_id] = to_path
 
1156
                    (None, target_kind),
 
1157
                    (None, target_executable))
 
1158
            source_path, source_entry = from_data.get(target_entry.file_id,
 
1159
                (None, None))
 
1160
            result, changes = self._changes_from_entries(source_entry,
 
1161
                target_entry, source_path=source_path, target_path=target_path)
 
1162
            to_paths[result[0]] = result[1][1]
961
1163
            entry_count += 1
962
 
            changed_content = False
963
 
            from_path, from_entry = from_data.get(file_id, (None, None))
964
 
            from_versioned = (from_entry is not None)
965
 
            if from_entry is not None:
966
 
                from_versioned = True
967
 
                from_name = from_entry.name
968
 
                from_parent = from_entry.parent_id
969
 
                from_kind, from_executable, from_stat = \
970
 
                    self.source._comparison_data(from_entry, from_path)
 
1164
            if result[3][0]:
971
1165
                entry_count += 1
972
 
            else:
973
 
                from_versioned = False
974
 
                from_kind = None
975
 
                from_parent = None
976
 
                from_name = None
977
 
                from_executable = None
978
 
            versioned = (from_versioned, True)
979
 
            to_kind, to_executable, to_stat = \
980
 
                self.target._comparison_data(to_entry, to_path)
981
 
            kind = (from_kind, to_kind)
982
 
            if kind[0] != kind[1]:
983
 
                changed_content = True
984
 
            elif from_kind == 'file':
985
 
                if (self.source.get_file_sha1(file_id, from_path, from_stat) !=
986
 
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
987
 
                    changed_content = True
988
 
            elif from_kind == 'symlink':
989
 
                if (self.source.get_symlink_target(file_id) !=
990
 
                    self.target.get_symlink_target(file_id)):
991
 
                    changed_content = True
992
 
                # XXX: Yes, the indentation below is wrong. But fixing it broke
993
 
                # test_merge.TestMergerEntriesLCAOnDisk.
994
 
                # test_nested_tree_subtree_renamed_and_modified. We'll wait for
995
 
                # the fix from bzr.dev -- vila 2009026
996
 
                elif from_kind == 'tree-reference':
997
 
                    if (self.source.get_reference_revision(file_id, from_path)
998
 
                        != self.target.get_reference_revision(file_id, to_path)):
999
 
                        changed_content = True
1000
 
            parent = (from_parent, to_entry.parent_id)
1001
 
            name = (from_name, to_entry.name)
1002
 
            executable = (from_executable, to_executable)
1003
1166
            if pb is not None:
1004
1167
                pb.update('comparing files', entry_count, num_entries)
1005
 
            if (changed_content is not False or versioned[0] != versioned[1]
1006
 
                or parent[0] != parent[1] or name[0] != name[1] or
1007
 
                executable[0] != executable[1] or include_unchanged):
1008
 
                yield (file_id, (from_path, to_path), changed_content,
1009
 
                    versioned, parent, name, kind, executable)
1010
 
 
 
1168
            if changes or include_unchanged:
 
1169
                if specific_file_ids is not None:
 
1170
                    new_parent_id = result[4][1]
 
1171
                    precise_file_ids.add(new_parent_id)
 
1172
                    changed_file_ids.append(result[0])
 
1173
                yield result
 
1174
            # Ensure correct behaviour for reparented/added specific files.
 
1175
            if specific_files is not None:
 
1176
                # Record output dirs
 
1177
                if result[6][1] == 'directory':
 
1178
                    seen_dirs.add(result[0])
 
1179
                # Record parents of reparented/added entries.
 
1180
                versioned = result[3]
 
1181
                parents = result[4]
 
1182
                if not versioned[0] or parents[0] != parents[1]:
 
1183
                    seen_parents.add(parents[1])
1011
1184
        while all_unversioned:
1012
1185
            # yield any trailing unversioned paths
1013
1186
            unversioned_path = all_unversioned.popleft()
1018
1191
                (None, unversioned_path[0][-1]),
1019
1192
                (None, to_kind),
1020
1193
                (None, to_executable))
1021
 
 
1022
 
        def get_to_path(to_entry):
1023
 
            if to_entry.parent_id is None:
1024
 
                to_path = '' # the root
1025
 
            else:
1026
 
                if to_entry.parent_id not in to_paths:
1027
 
                    # recurse up
1028
 
                    return get_to_path(self.target.inventory[to_entry.parent_id])
1029
 
                to_path = osutils.pathjoin(to_paths[to_entry.parent_id],
1030
 
                                           to_entry.name)
1031
 
            to_paths[to_entry.file_id] = to_path
1032
 
            return to_path
1033
 
 
 
1194
        # Yield all remaining source paths
1034
1195
        for path, from_entry in from_entries_by_dir:
1035
1196
            file_id = from_entry.file_id
1036
1197
            if file_id in to_paths:
1037
1198
                # already returned
1038
1199
                continue
1039
 
            if not file_id in self.target.all_file_ids():
 
1200
            if not self.target.has_id(file_id):
1040
1201
                # common case - paths we have not emitted are not present in
1041
1202
                # target.
1042
1203
                to_path = None
1043
1204
            else:
1044
 
                to_path = get_to_path(self.target.inventory[file_id])
 
1205
                to_path = self.target.id2path(file_id)
1045
1206
            entry_count += 1
1046
1207
            if pb is not None:
1047
1208
                pb.update('comparing files', entry_count, num_entries)
1054
1215
            executable = (from_executable, None)
1055
1216
            changed_content = from_kind is not None
1056
1217
            # the parent's path is necessarily known at this point.
 
1218
            changed_file_ids.append(file_id)
1057
1219
            yield(file_id, (path, to_path), changed_content, versioned, parent,
1058
1220
                  name, kind, executable)
 
1221
        changed_file_ids = set(changed_file_ids)
 
1222
        if specific_file_ids is not None:
 
1223
            for result in self._handle_precise_ids(precise_file_ids,
 
1224
                changed_file_ids):
 
1225
                yield result
 
1226
 
 
1227
    def _get_entry(self, tree, file_id):
 
1228
        """Get an inventory entry from a tree, with missing entries as None.
 
1229
 
 
1230
        If the tree raises NotImplementedError on accessing .inventory, then
 
1231
        this is worked around using iter_entries_by_dir on just the file id
 
1232
        desired.
 
1233
 
 
1234
        :param tree: The tree to lookup the entry in.
 
1235
        :param file_id: The file_id to lookup.
 
1236
        """
 
1237
        try:
 
1238
            inventory = tree.inventory
 
1239
        except NotImplementedError:
 
1240
            # No inventory available.
 
1241
            try:
 
1242
                iterator = tree.iter_entries_by_dir(specific_file_ids=[file_id])
 
1243
                return iterator.next()[1]
 
1244
            except StopIteration:
 
1245
                return None
 
1246
        else:
 
1247
            try:
 
1248
                return inventory[file_id]
 
1249
            except errors.NoSuchId:
 
1250
                return None
 
1251
 
 
1252
    def _handle_precise_ids(self, precise_file_ids, changed_file_ids,
 
1253
        discarded_changes=None):
 
1254
        """Fill out a partial iter_changes to be consistent.
 
1255
 
 
1256
        :param precise_file_ids: The file ids of parents that were seen during
 
1257
            the iter_changes.
 
1258
        :param changed_file_ids: The file ids of already emitted items.
 
1259
        :param discarded_changes: An optional dict of precalculated
 
1260
            iter_changes items which the partial iter_changes had not output
 
1261
            but had calculated.
 
1262
        :return: A generator of iter_changes items to output.
 
1263
        """
 
1264
        # process parents of things that had changed under the users
 
1265
        # requested paths to prevent incorrect paths or parent ids which
 
1266
        # aren't in the tree.
 
1267
        while precise_file_ids:
 
1268
            precise_file_ids.discard(None)
 
1269
            # Don't emit file_ids twice
 
1270
            precise_file_ids.difference_update(changed_file_ids)
 
1271
            if not precise_file_ids:
 
1272
                break
 
1273
            # If the there was something at a given output path in source, we
 
1274
            # have to include the entry from source in the delta, or we would
 
1275
            # be putting this entry into a used path.
 
1276
            paths = []
 
1277
            for parent_id in precise_file_ids:
 
1278
                try:
 
1279
                    paths.append(self.target.id2path(parent_id))
 
1280
                except errors.NoSuchId:
 
1281
                    # This id has been dragged in from the source by delta
 
1282
                    # expansion and isn't present in target at all: we don't
 
1283
                    # need to check for path collisions on it.
 
1284
                    pass
 
1285
            for path in paths:
 
1286
                old_id = self.source.path2id(path)
 
1287
                precise_file_ids.add(old_id)
 
1288
            precise_file_ids.discard(None)
 
1289
            current_ids = precise_file_ids
 
1290
            precise_file_ids = set()
 
1291
            # We have to emit all of precise_file_ids that have been altered.
 
1292
            # We may have to output the children of some of those ids if any
 
1293
            # directories have stopped being directories.
 
1294
            for file_id in current_ids:
 
1295
                # Examine file_id
 
1296
                if discarded_changes:
 
1297
                    result = discarded_changes.get(file_id)
 
1298
                    old_entry = None
 
1299
                else:
 
1300
                    result = None
 
1301
                if result is None:
 
1302
                    old_entry = self._get_entry(self.source, file_id)
 
1303
                    new_entry = self._get_entry(self.target, file_id)
 
1304
                    result, changes = self._changes_from_entries(
 
1305
                        old_entry, new_entry)
 
1306
                else:
 
1307
                    changes = True
 
1308
                # Get this parents parent to examine.
 
1309
                new_parent_id = result[4][1]
 
1310
                precise_file_ids.add(new_parent_id)
 
1311
                if changes:
 
1312
                    if (result[6][0] == 'directory' and
 
1313
                        result[6][1] != 'directory'):
 
1314
                        # This stopped being a directory, the old children have
 
1315
                        # to be included.
 
1316
                        if old_entry is None:
 
1317
                            # Reusing a discarded change.
 
1318
                            old_entry = self._get_entry(self.source, file_id)
 
1319
                        for child in old_entry.children.values():
 
1320
                            precise_file_ids.add(child.file_id)
 
1321
                    changed_file_ids.add(result[0])
 
1322
                    yield result
 
1323
 
 
1324
 
 
1325
InterTree.register_optimiser(InterTree)
1059
1326
 
1060
1327
 
1061
1328
class MultiWalker(object):