~bzr-pqm/bzr/bzr.dev

5752.3.8 by John Arbash Meinel
Merge bzr.dev 5764 to resolve release-notes (aka NEWS) conflicts
1
# Copyright (C) 2005-2011 Canonical Ltd
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
2
#
1 by mbp at sourcefrog
import from baz patch-364
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
7
#
1 by mbp at sourcefrog
import from baz patch-364
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
# GNU General Public License for more details.
1887.1.1 by Adeodato Simó
Do not separate paragraphs in the copyright statement with blank lines,
12
#
1 by mbp at sourcefrog
import from baz patch-364
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
4183.7.1 by Sabin Iacob
update FSF mailing address
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
1 by mbp at sourcefrog
import from baz patch-364
16
17
"""Tree classes, representing directory at point in time.
18
"""
19
849 by Martin Pool
- Put files inside an exported tarball into a top-level directory rather than
20
import os
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
21
22
from bzrlib.lazy_import import lazy_import
23
lazy_import(globals(), """
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
24
import collections
800 by Martin Pool
Merge John's import-speedup branch:
25
2079.1.1 by John Arbash Meinel
Create a deprecated bzrlib.tree.RevisionTree() in favor of bzrlib.revisiontree.RevisionTree()
26
from bzrlib import (
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
27
    conflicts as _mod_conflicts,
3368.2.30 by Ian Clatworthy
add -Dfilters support
28
    debug,
2079.1.1 by John Arbash Meinel
Create a deprecated bzrlib.tree.RevisionTree() in favor of bzrlib.revisiontree.RevisionTree()
29
    delta,
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
30
    errors,
3368.2.16 by Ian Clatworthy
add real implementation of Tree.get_filter_stack
31
    filters,
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
32
    inventory,
2012.1.8 by Aaron Bentley
Merge from bzr.dev
33
    osutils,
1551.15.46 by Aaron Bentley
Move plan merge to tree
34
    revision as _mod_revision,
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
35
    rules,
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
36
    trace,
2079.1.1 by John Arbash Meinel
Create a deprecated bzrlib.tree.RevisionTree() in favor of bzrlib.revisiontree.RevisionTree()
37
    )
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
38
""")
39
1852.11.1 by Robert Collins
Deprecate compare_trees and move its body to InterTree.changes_from.
40
from bzrlib.decorators import needs_read_lock
1852.8.2 by Robert Collins
Add InterTree class to represent InterTree operations.
41
from bzrlib.inter import InterObject
1 by mbp at sourcefrog
import from baz patch-364
42
1852.5.1 by Robert Collins
Deprecate EmptyTree in favour of using Repository.revision_tree.
43
558 by Martin Pool
- All top-level classes inherit from object
44
class Tree(object):
1 by mbp at sourcefrog
import from baz patch-364
45
    """Abstract file tree.
46
47
    There are several subclasses:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
48
1 by mbp at sourcefrog
import from baz patch-364
49
    * `WorkingTree` exists as files on disk editable by the user.
50
51
    * `RevisionTree` is a tree as recorded at some point in the past.
52
53
    Trees can be compared, etc, regardless of whether they are working
54
    trees or versioned trees.
55
    """
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
56
1852.9.6 by Robert Collins
Merge the change from Tree.compare to Tree.changes_from.
57
    def changes_from(self, other, want_unchanged=False, specific_files=None,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
58
        extra_trees=None, require_versioned=False, include_root=False,
59
        want_unversioned=False):
1852.8.8 by Robert Collins
change Tree.compare to Tree.changes_from - its better for the common case.
60
        """Return a TreeDelta of the changes from other to this tree.
1852.9.3 by Robert Collins
Convert the test_delta tests to intertree_implementation and workingtree_implementation tests as appropriate.
61
62
        :param other: A tree to compare with.
63
        :param specific_files: An optional list of file paths to restrict the
64
            comparison to. When mapping filenames to ids, all matches in all
65
            trees (including optional extra_trees) are used, and all children of
66
            matched directories are included.
1852.9.4 by Robert Collins
Add minimal test for Tree.compare(extra_trees=...).
67
        :param want_unchanged: An optional boolean requesting the inclusion of
68
            unchanged entries in the result.
69
        :param extra_trees: An optional list of additional trees to use when
70
            mapping the contents of specific_files (paths) to file_ids.
1852.9.5 by Robert Collins
Add tests for require_versioned to the InterTree.compare() test suite.
71
        :param require_versioned: An optional boolean (defaults to False). When
72
            supplied and True all the 'specific_files' must be versioned, or
73
            a PathsNotVersionedError will be thrown.
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
74
        :param want_unversioned: Scan for unversioned paths.
1852.9.3 by Robert Collins
Convert the test_delta tests to intertree_implementation and workingtree_implementation tests as appropriate.
75
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
76
        The comparison will be performed by an InterTree object looked up on
1852.8.4 by Robert Collins
Hook InterTree into Tree.
77
        self and other.
78
        """
1852.8.8 by Robert Collins
change Tree.compare to Tree.changes_from - its better for the common case.
79
        # Martin observes that Tree.changes_from returns a TreeDelta and this
80
        # may confuse people, because the class name of the returned object is
81
        # a synonym of the object referenced in the method name.
1852.9.6 by Robert Collins
Merge the change from Tree.compare to Tree.changes_from.
82
        return InterTree.get(other, self).compare(
1852.9.4 by Robert Collins
Add minimal test for Tree.compare(extra_trees=...).
83
            want_unchanged=want_unchanged,
84
            specific_files=specific_files,
1852.9.5 by Robert Collins
Add tests for require_versioned to the InterTree.compare() test suite.
85
            extra_trees=extra_trees,
86
            require_versioned=require_versioned,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
87
            include_root=include_root,
88
            want_unversioned=want_unversioned,
1852.9.5 by Robert Collins
Add tests for require_versioned to the InterTree.compare() test suite.
89
            )
2012.1.1 by Aaron Bentley
Implement change iterator
90
3254.1.1 by Aaron Bentley
Make Tree.iter_changes a public method
91
    def iter_changes(self, from_tree, include_unchanged=False,
2255.2.149 by Robert Collins
Crufty but existing _iter_changes implementation for WorkingTreeFormat4.
92
                     specific_files=None, pb=None, extra_trees=None,
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
93
                     require_versioned=True, want_unversioned=False):
4988.10.6 by John Arbash Meinel
Fix bug #304182 by adding a trivial docstring to Tree.iter_changes
94
        """See InterTree.iter_changes"""
2012.1.5 by Aaron Bentley
Implement specific file id and dangling id handling
95
        intertree = InterTree.get(from_tree, self)
3254.1.1 by Aaron Bentley
Make Tree.iter_changes a public method
96
        return intertree.iter_changes(include_unchanged, specific_files, pb,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
97
            extra_trees, require_versioned, want_unversioned=want_unversioned)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
98
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
99
    def conflicts(self):
100
        """Get a list of the conflicts in the tree.
101
102
        Each conflict is an instance of bzrlib.conflicts.Conflict.
103
        """
2748.2.1 by Lukáš Lalinsky
Return ConflictsList() instead of [] from Tree.conflicts.
104
        return _mod_conflicts.ConflictList()
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
105
2255.7.91 by Robert Collins
Move unknown detection in long status into the delta creation, saving a tree-scan.
106
    def extras(self):
107
        """For trees that can have unversioned files, return all such paths."""
108
        return []
109
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
110
    def get_parent_ids(self):
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
111
        """Get the parent ids for this tree.
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
112
113
        :return: a list of parent ids. [] is returned to indicate
114
        a tree with no parents.
115
        :raises: BzrError if the parents are not known.
116
        """
117
        raise NotImplementedError(self.get_parent_ids)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
118
1 by mbp at sourcefrog
import from baz patch-364
119
    def has_filename(self, filename):
120
        """True if the tree has given filename."""
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
121
        raise NotImplementedError(self.has_filename)
1 by mbp at sourcefrog
import from baz patch-364
122
1185.12.39 by abentley
Propogated has_or_had_id to Tree
123
    def has_id(self, file_id):
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
124
        raise NotImplementedError(self.has_id)
1185.12.39 by abentley
Propogated has_or_had_id to Tree
125
3363.15.3 by Aaron Bentley
Change Tree.__contains__ to tolerate subclasssing
126
    def __contains__(self, file_id):
127
        return self.has_id(file_id)
1852.6.9 by Robert Collins
Add more test trees to the tree-implementations tests.
128
1185.12.39 by abentley
Propogated has_or_had_id to Tree
129
    def has_or_had_id(self, file_id):
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
130
        raise NotImplementedError(self.has_or_had_id)
1 by mbp at sourcefrog
import from baz patch-364
131
2255.7.97 by Robert Collins
Teach delta.report_changes about unversioned files, removing all inventory access during status --short.
132
    def is_ignored(self, filename):
133
        """Check whether the filename is ignored by this tree.
134
135
        :param filename: The relative filename within the tree.
136
        :return: True if the filename is ignored.
137
        """
138
        return False
139
462 by Martin Pool
- New form 'file_id in tree' to check if the file is present
140
    def __iter__(self):
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
141
        """Yield all file ids in this tree."""
142
        raise NotImplementedError(self.__iter__)
462 by Martin Pool
- New form 'file_id in tree' to check if the file is present
143
3146.8.16 by Aaron Bentley
Updates from review
144
    def all_file_ids(self):
3146.8.2 by Aaron Bentley
Introduce iter_all_file_ids, to avoid hitting Inventory for this case
145
        """Iterate through all file ids, including ids for missing files."""
3146.8.16 by Aaron Bentley
Updates from review
146
        return set(self.inventory)
3146.8.2 by Aaron Bentley
Introduce iter_all_file_ids, to avoid hitting Inventory for this case
147
1 by mbp at sourcefrog
import from baz patch-364
148
    def id2path(self, file_id):
2255.11.5 by Martin Pool
Tree.id2path should raise NoSuchId, not return None.
149
        """Return the path for a file id.
150
151
        :raises NoSuchId:
152
        """
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
153
        raise NotImplementedError(self.id2path)
1 by mbp at sourcefrog
import from baz patch-364
154
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
155
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
1852.6.9 by Robert Collins
Add more test trees to the tree-implementations tests.
156
        """Walk the tree in 'by_dir' order.
157
3363.2.23 by Aaron Bentley
Fix iter_entries_by_dir ordering
158
        This will yield each entry in the tree as a (path, entry) tuple.
159
        The order that they are yielded is:
160
161
        Directories are walked in a depth-first lexicographical order,
162
        however, whenever a directory is reached, all of its direct child
163
        nodes are yielded in  lexicographical order before yielding the
164
        grandchildren.
165
166
        For example, in the tree::
167
168
           a/
169
             b/
170
               c
171
             d/
172
               e
173
           f/
174
             g
175
3363.5.4 by Aaron Bentley
Fix iteration order of iter_entries_by_dir
176
        The yield order (ignoring root) would be::
3363.2.23 by Aaron Bentley
Fix iter_entries_by_dir ordering
177
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
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.
1852.6.9 by Robert Collins
Add more test trees to the tree-implementations tests.
182
        """
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
183
        raise NotImplementedError(self.iter_entries_by_dir)
1852.6.9 by Robert Collins
Add more test trees to the tree-implementations tests.
184
5793.2.1 by Jelmer Vernooij
Add Tree.list_files stub.
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)
195
2255.2.226 by Robert Collins
Get merge_nested finally working: change nested tree iterators to take file_ids, and ensure the right branch is connected to in the merge logic. May not be suitable for shared repositories yet.
196
    def iter_references(self):
4370.3.2 by Ian Clatworthy
apply jam's review feedback
197
        if self.supports_tree_reference():
198
            for path, entry in self.iter_entries_by_dir():
199
                if entry.kind == 'tree-reference':
200
                    yield path, entry.file_id
2100.3.27 by Aaron Bentley
Enable nested commits
201
1465 by Robert Collins
Bugfix the new pull --clobber to not generate spurious conflicts.
202
    def kind(self, file_id):
2255.2.159 by Martin Pool
reference-trees in dirstate pass all tests.
203
        raise NotImplementedError("Tree subclass %s must implement kind"
204
            % self.__class__.__name__)
1465 by Robert Collins
Bugfix the new pull --clobber to not generate spurious conflicts.
205
3146.8.4 by Aaron Bentley
Eliminate direct use of inventory from transform application
206
    def stored_kind(self, file_id):
207
        """File kind stored for this file_id.
208
3146.8.15 by Aaron Bentley
Cleanup and docs
209
        May not match kind on disk for working trees.  Always available
210
        for versioned files, even when the file itself is missing.
3146.8.4 by Aaron Bentley
Eliminate direct use of inventory from transform application
211
        """
212
        return self.kind(file_id)
213
2776.1.7 by Robert Collins
* New method on ``bzrlib.tree.Tree`` ``path_content_summary`` provides a
214
    def path_content_summary(self, path):
215
        """Get a summary of the information about path.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
216
4595.11.2 by Martin Pool
Clarify contract of path_content_summary
217
        All the attributes returned are for the canonical form, not the
218
        convenient form (if content filters are in use.)
219
2776.1.7 by Robert Collins
* New method on ``bzrlib.tree.Tree`` ``path_content_summary`` provides a
220
        :param path: A relative path within the tree.
221
        :return: A tuple containing kind, size, exec, sha1-or-link.
222
            Kind is always present (see tree.kind()).
4595.11.13 by Martin Pool
Remove get_kind_and_executable_by_path; go back to using plain path_content_summary
223
            size is present if kind is file and the size of the 
224
                canonical form can be cheaply determined, None otherwise.
2776.1.7 by Robert Collins
* New method on ``bzrlib.tree.Tree`` ``path_content_summary`` provides a
225
            exec is None unless kind is file and the platform supports the 'x'
226
                bit.
227
            sha1-or-link is the link target if kind is symlink, or the sha1 if
228
                it can be obtained without reading the file.
229
        """
230
        raise NotImplementedError(self.path_content_summary)
231
2255.2.226 by Robert Collins
Get merge_nested finally working: change nested tree iterators to take file_ids, and ensure the right branch is connected to in the merge logic. May not be suitable for shared repositories yet.
232
    def get_reference_revision(self, file_id, path=None):
2255.2.158 by Martin Pool
Most of the integration of dirstate and subtree
233
        raise NotImplementedError("Tree subclass %s must implement "
234
                                  "get_reference_revision"
235
            % self.__class__.__name__)
2100.3.20 by Aaron Bentley
Implement tree comparison for tree references
236
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
237
    def _comparison_data(self, entry, path):
2012.1.15 by Aaron Bentley
Minor tweaks
238
        """Return a tuple of kind, executable, stat_value for a file.
239
240
        entry may be None if there is no inventory entry for the file, but
241
        path must always be supplied.
242
243
        kind is None if there is no file present (even if an inventory id is
244
        present).  executable is False for non-file entries.
245
        """
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
246
        raise NotImplementedError(self._comparison_data)
247
2255.2.10 by Robert Collins
Now all tests matching dirstate pass - added generation of inventories for parent trees.
248
    def _file_size(self, entry, stat_value):
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
249
        raise NotImplementedError(self._file_size)
250
2743.3.3 by Ian Clatworthy
Skip path lookup for tree.get_file() when we already know the path
251
    def get_file(self, file_id, path=None):
2772.2.1 by Ian Clatworthy
(Ian Clatworthy) Quicker initial commit - skip SHAing twice & skip path lookup as we know it
252
        """Return a file object for the file file_id in the tree.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
253
2772.2.1 by Ian Clatworthy
(Ian Clatworthy) Quicker initial commit - skip SHAing twice & skip path lookup as we know it
254
        If both file_id and path are defined, it is implementation defined as
255
        to which one is used.
256
        """
1986.1.2 by Robert Collins
Various changes to allow non-workingtree specific tests to run entirely
257
        raise NotImplementedError(self.get_file)
2255.7.36 by John Arbash Meinel
All trees should implement get_file_mtime()
258
4354.4.5 by Aaron Bentley
Ensure Tree.get_file_with_stat is provided.
259
    def get_file_with_stat(self, file_id, path=None):
4354.4.7 by Aaron Bentley
Move MutableTree.get_file_with_stat to Tree.get_file_with_stat.
260
        """Get a file handle and stat object for file_id.
261
262
        The default implementation returns (self.get_file, None) for backwards
263
        compatibility.
264
265
        :param file_id: The file id to read.
266
        :param path: The path of the file, if it is known.
267
        :return: A tuple (file_handle, stat_value_or_None). If the tree has
268
            no stat facility, or need for a stat cache feedback during commit,
269
            it may return None for the second element of the tuple.
270
        """
271
        return (self.get_file(file_id, path), None)
4354.4.5 by Aaron Bentley
Ensure Tree.get_file_with_stat is provided.
272
3774.1.1 by Aaron Bentley
Test Tree.get_file_text() and supply default implementation.
273
    def get_file_text(self, file_id, path=None):
274
        """Return the byte content of a file.
275
276
        :param file_id: The file_id of the file.
277
        :param path: The path of the file.
278
        If both file_id and path are supplied, an implementation may use
279
        either one.
280
        """
281
        my_file = self.get_file(file_id, path)
282
        try:
283
            return my_file.read()
284
        finally:
285
            my_file.close()
286
3774.1.2 by Aaron Bentley
Test Tree.get_file_lines, provide a default implementation
287
    def get_file_lines(self, file_id, path=None):
288
        """Return the content of a file, as lines.
289
290
        :param file_id: The file_id of the file.
291
        :param path: The path of the file.
292
        If both file_id and path are supplied, an implementation may use
293
        either one.
294
        """
295
        return osutils.split_lines(self.get_file_text(file_id, path))
296
5777.1.3 by Jelmer Vernooij
Add stub for Tree.get_file_sha1.
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
2255.7.36 by John Arbash Meinel
All trees should implement get_file_mtime()
306
    def get_file_mtime(self, file_id, path=None):
307
        """Return the modification time for a file.
308
309
        :param file_id: The handle for this file.
310
        :param path: The path that this file can be found at.
311
            These must point to the same object.
312
        """
313
        raise NotImplementedError(self.get_file_mtime)
314
3363.3.4 by Aaron Bentley
Add get_file_size to Tree interface
315
    def get_file_size(self, file_id):
316
        """Return the size of a file in bytes.
317
318
        This applies only to regular files.  If invoked on directories or
319
        symlinks, it will return None.
320
        :param file_id: The file-id of the file
321
        """
322
        raise NotImplementedError(self.get_file_size)
323
974.1.26 by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472
324
    def get_file_by_path(self, path):
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
325
        raise NotImplementedError(self.get_file_by_path)
1 by mbp at sourcefrog
import from baz patch-364
326
5777.1.4 by Jelmer Vernooij
Stub for is_executable.
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)
335
2708.1.7 by Aaron Bentley
Rename extract_files_bytes to iter_files_bytes
336
    def iter_files_bytes(self, desired_files):
2708.1.6 by Aaron Bentley
Turn extract_files_bytes into an iterator
337
        """Iterate through file contents.
2708.1.1 by Aaron Bentley
Implement Tree.extract_files
338
2708.1.10 by Aaron Bentley
Update docstrings
339
        Files will not necessarily be returned in the order they occur in
340
        desired_files.  No specific order is guaranteed.
341
342
        Yields pairs of identifier, bytes_iterator.  identifier is an opaque
343
        value supplied by the caller as part of desired_files.  It should
344
        uniquely identify the file version in the caller's context.  (Examples:
345
        an index number or a TreeTransform trans_id.)
346
347
        bytes_iterator is an iterable of bytestrings for the file.  The
348
        kind of iterable and length of the bytestrings are unspecified, but for
349
        this implementation, it is a tuple containing a single bytestring with
350
        the complete text of the file.
351
2708.1.6 by Aaron Bentley
Turn extract_files_bytes into an iterator
352
        :param desired_files: a list of (file_id, identifier) pairs
2708.1.1 by Aaron Bentley
Implement Tree.extract_files
353
        """
2708.1.6 by Aaron Bentley
Turn extract_files_bytes into an iterator
354
        for file_id, identifier in desired_files:
2708.1.10 by Aaron Bentley
Update docstrings
355
            # We wrap the string in a tuple so that we can return an iterable
356
            # of bytestrings.  (Technically, a bytestring is also an iterable
357
            # of bytestrings, but iterating through each character is not
358
            # performant.)
2708.1.6 by Aaron Bentley
Turn extract_files_bytes into an iterator
359
            cur_file = (self.get_file_text(file_id),)
360
            yield identifier, cur_file
2708.1.1 by Aaron Bentley
Implement Tree.extract_files
361
2255.2.134 by John Arbash Meinel
Add a tree-test for get_symlink_target
362
    def get_symlink_target(self, file_id):
363
        """Get the target for a given file_id.
364
365
        It is assumed that the caller already knows that file_id is referencing
366
        a symlink.
367
        :param file_id: Handle for the symlink entry.
368
        :return: The path the symlink points to.
369
        """
370
        raise NotImplementedError(self.get_symlink_target)
371
3794.5.5 by Mark Hammond
Add get_canonical_path method to the Tree class, plus tests.
372
2946.3.2 by John Arbash Meinel
Add tree implementation tests for Tree.get_root_id()
373
    def get_root_id(self):
374
        """Return the file_id for the root of this tree."""
375
        raise NotImplementedError(self.get_root_id)
376
3224.1.2 by John Arbash Meinel
Updated the base Tree.annotate_iter() since all implemenations take an optional kwarg.
377
    def annotate_iter(self, file_id,
378
                      default_revision=_mod_revision.CURRENT_REVISION):
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
379
        """Return an iterator of revision_id, line tuples.
1551.9.18 by Aaron Bentley
Updates from review comments
380
1551.9.16 by Aaron Bentley
Implement Tree.annotate_iter for RevisionTree and WorkingTree
381
        For working trees (and mutable trees in general), the special
382
        revision_id 'current:' will be used for lines that are new in this
383
        tree, e.g. uncommitted changes.
384
        :param file_id: The file to produce an annotated version from
3224.1.2 by John Arbash Meinel
Updated the base Tree.annotate_iter() since all implemenations take an optional kwarg.
385
        :param default_revision: For lines that don't match a basis, mark them
386
            with this revision id. Not all implementations will make use of
387
            this value.
1551.9.16 by Aaron Bentley
Implement Tree.annotate_iter for RevisionTree and WorkingTree
388
        """
389
        raise NotImplementedError(self.annotate_iter)
390
3144.3.1 by Aaron Bentley
Implement LCA merge, with problematic conflict markers
391
    def _get_plan_merge_data(self, file_id, other, base):
4496.3.15 by Andrew Bennetts
Remove unused imports.
392
        from bzrlib import versionedfile
3062.1.11 by Aaron Bentley
Update references
393
        vf = versionedfile._PlanMergeVersionedFile(file_id)
3062.1.3 by Aaron Bentley
Correctly determine file revisions
394
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
395
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
3062.2.4 by Aaron Bentley
Start supporting merge-with-base
396
        if base is None:
397
            last_revision_base = None
398
        else:
3062.2.6 by Aaron Bentley
Get cherrypick-on-weave working
399
            last_revision_base = base._get_file_revision(file_id, vf, 'base:')
3144.3.1 by Aaron Bentley
Implement LCA merge, with problematic conflict markers
400
        return vf, last_revision_a, last_revision_b, last_revision_base
401
402
    def plan_file_merge(self, file_id, other, base=None):
403
        """Generate a merge plan based on annotations.
404
405
        If the file contains uncommitted changes in this tree, they will be
406
        attributed to the 'current:' pseudo-revision.  If the file contains
407
        uncommitted changes in the other tree, they will be assigned to the
408
        'other:' pseudo-revision.
409
        """
410
        data = self._get_plan_merge_data(file_id, other, base)
411
        vf, last_revision_a, last_revision_b, last_revision_base = data
3062.2.4 by Aaron Bentley
Start supporting merge-with-base
412
        return vf.plan_merge(last_revision_a, last_revision_b,
413
                             last_revision_base)
3062.1.3 by Aaron Bentley
Correctly determine file revisions
414
3144.3.1 by Aaron Bentley
Implement LCA merge, with problematic conflict markers
415
    def plan_file_lca_merge(self, file_id, other, base=None):
416
        """Generate a merge plan based lca-newness.
417
418
        If the file contains uncommitted changes in this tree, they will be
419
        attributed to the 'current:' pseudo-revision.  If the file contains
420
        uncommitted changes in the other tree, they will be assigned to the
421
        'other:' pseudo-revision.
422
        """
423
        data = self._get_plan_merge_data(file_id, other, base)
424
        vf, last_revision_a, last_revision_b, last_revision_base = data
425
        return vf.plan_lca_merge(last_revision_a, last_revision_b,
426
                                 last_revision_base)
427
3363.9.1 by Aaron Bentley
Implement plan_merge, refactoring various bits
428
    def _iter_parent_trees(self):
429
        """Iterate through parent trees, defaulting to Tree.revision_tree."""
430
        for revision_id in self.get_parent_ids():
431
            try:
432
                yield self.revision_tree(revision_id)
433
            except errors.NoSuchRevisionInTree:
434
                yield self.repository.revision_tree(revision_id)
435
3062.1.3 by Aaron Bentley
Correctly determine file revisions
436
    def _get_file_revision(self, file_id, vf, tree_revision):
3350.6.4 by Robert Collins
First cut at pluralised VersionedFiles. Some rather massive API incompatabilities, primarily because of the difficulty of coherence among competing stores.
437
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
3062.1.3 by Aaron Bentley
Correctly determine file revisions
438
3350.6.4 by Robert Collins
First cut at pluralised VersionedFiles. Some rather massive API incompatabilities, primarily because of the difficulty of coherence among competing stores.
439
        if getattr(self, '_repository', None) is None:
3062.1.3 by Aaron Bentley
Correctly determine file revisions
440
            last_revision = tree_revision
5793.2.3 by Jelmer Vernooij
Add a RevisionTree.get_file_revision() method.
441
            parent_keys = [(file_id, t.get_file_revision(file_id)) for t in
3363.9.1 by Aaron Bentley
Implement plan_merge, refactoring various bits
442
                self._iter_parent_trees()]
3350.6.4 by Robert Collins
First cut at pluralised VersionedFiles. Some rather massive API incompatabilities, primarily because of the difficulty of coherence among competing stores.
443
            vf.add_lines((file_id, last_revision), parent_keys,
4708.2.1 by Martin
Ensure all files opened by bazaar proper are explicitly closed
444
                         self.get_file_lines(file_id))
3062.1.6 by Aaron Bentley
PlanMergeVersionedfile now has multiple Versionedfile fallbacks
445
            repo = self.branch.repository
3350.6.4 by Robert Collins
First cut at pluralised VersionedFiles. Some rather massive API incompatabilities, primarily because of the difficulty of coherence among competing stores.
446
            base_vf = repo.texts
3062.1.3 by Aaron Bentley
Correctly determine file revisions
447
        else:
5793.2.3 by Jelmer Vernooij
Add a RevisionTree.get_file_revision() method.
448
            last_revision = self.get_file_revision(file_id)
3350.6.4 by Robert Collins
First cut at pluralised VersionedFiles. Some rather massive API incompatabilities, primarily because of the difficulty of coherence among competing stores.
449
            base_vf = self._repository.texts
450
        if base_vf not in vf.fallback_versionedfiles:
451
            vf.fallback_versionedfiles.append(base_vf)
3062.1.3 by Aaron Bentley
Correctly determine file revisions
452
        return last_revision
1551.15.46 by Aaron Bentley
Move plan merge to tree
453
1 by mbp at sourcefrog
import from baz patch-364
454
    def _check_retrieved(self, ie, f):
1364 by Martin Pool
- remove extra verification of files retrieved from tree
455
        if not __debug__:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
456
            return
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
457
        fp = osutils.fingerprint_file(f)
130 by mbp at sourcefrog
- fixup checks on retrieved files to cope with compression,
458
        f.seek(0)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
459
1963.2.6 by Robey Pointer
pychecker is on crack; go back to using 'is None'.
460
        if ie.text_size is not None:
131 by mbp at sourcefrog
check size and sha1 of files retrieved from the tree
461
            if ie.text_size != fp['size']:
5753.2.2 by Jelmer Vernooij
Remove some unnecessary imports, clean up lazy imports.
462
                raise errors.BzrError(
463
                        "mismatched size for file %r in %r" %
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
464
                        (ie.file_id, self._store),
1 by mbp at sourcefrog
import from baz patch-364
465
                        ["inventory expects %d bytes" % ie.text_size,
130 by mbp at sourcefrog
- fixup checks on retrieved files to cope with compression,
466
                         "file is actually %d bytes" % fp['size'],
1 by mbp at sourcefrog
import from baz patch-364
467
                         "store is probably damaged/corrupt"])
468
130 by mbp at sourcefrog
- fixup checks on retrieved files to cope with compression,
469
        if ie.text_sha1 != fp['sha1']:
5745.3.1 by Jelmer Vernooij
Use lazy imports in bzrlib.tree.
470
            raise errors.BzrError("wrong SHA-1 for file %r in %r" %
471
                    (ie.file_id, self._store),
1 by mbp at sourcefrog
import from baz patch-364
472
                    ["inventory expects %s" % ie.text_sha1,
130 by mbp at sourcefrog
- fixup checks on retrieved files to cope with compression,
473
                     "file is actually %s" % fp['sha1'],
1 by mbp at sourcefrog
import from baz patch-364
474
                     "store is probably damaged/corrupt"])
475
1986.1.2 by Robert Collins
Various changes to allow non-workingtree specific tests to run entirely
476
    def path2id(self, path):
477
        """Return the id for path in this tree."""
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
478
        raise NotImplementedError(self.path2id)
1 by mbp at sourcefrog
import from baz patch-364
479
2255.2.101 by Robert Collins
Finish making Tree.ids2paths support the file_ids_across_trees api.
480
    def paths2ids(self, paths, trees=[], require_versioned=True):
2255.2.100 by Robert Collins
Create a paths2ids api to replace find_ids_across_trees, with tests.
481
        """Return all the ids that can be reached by walking from paths.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
482
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
483
        Each path is looked up in this tree and any extras provided in
2255.2.100 by Robert Collins
Create a paths2ids api to replace find_ids_across_trees, with tests.
484
        trees, and this is repeated recursively: the children in an extra tree
485
        of a directory that has been renamed under a provided path in this tree
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
486
        are all returned, even if none exist under a provided path in this
2255.2.100 by Robert Collins
Create a paths2ids api to replace find_ids_across_trees, with tests.
487
        tree, and vice versa.
2255.2.101 by Robert Collins
Finish making Tree.ids2paths support the file_ids_across_trees api.
488
489
        :param paths: An iterable of paths to start converting to ids from.
2255.2.104 by Robert Collins
Add WorkingTree4.paths2ids which is inventory-usage free if the trees being examined are in the dirstate.
490
            Alternatively, if paths is None, no ids should be calculated and None
491
            will be returned. This is offered to make calling the api unconditional
492
            for code that *might* take a list of files.
2255.2.101 by Robert Collins
Finish making Tree.ids2paths support the file_ids_across_trees api.
493
        :param trees: Additional trees to consider.
494
        :param require_versioned: If False, do not raise NotVersionedError if
495
            an element of paths is not versioned in this tree and all of trees.
2255.2.100 by Robert Collins
Create a paths2ids api to replace find_ids_across_trees, with tests.
496
        """
2255.2.105 by Robert Collins
Unfuck InterTree.compare which I broke with the paths2ids implementation.
497
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
2255.2.100 by Robert Collins
Create a paths2ids api to replace find_ids_across_trees, with tests.
498
3363.12.2 by Aaron Bentley
Implement tree.iter_children to instead of adjusting InventoryEntry handling
499
    def iter_children(self, file_id):
500
        entry = self.iter_entries_by_dir([file_id]).next()[1]
501
        for child in getattr(entry, 'children', {}).itervalues():
502
            yield child.file_id
503
1543.1.1 by Denys Duchier
lock operations for trees - use them for diff
504
    def lock_read(self):
5200.3.6 by Robert Collins
Make all lock methods return Result objects, rather than lock_read returning self, as per John's review.
505
        """Lock this tree for multiple read only operations.
506
        
507
        :return: A bzrlib.lock.LogicalLockResult.
508
        """
1543.1.1 by Denys Duchier
lock operations for trees - use them for diff
509
        pass
510
1908.11.1 by Robert Collins
Add a new method ``Tree.revision_tree`` which allows access to cached
511
    def revision_tree(self, revision_id):
512
        """Obtain a revision tree for the revision revision_id.
513
514
        The intention of this method is to allow access to possibly cached
515
        tree data. Implementors of this method should raise NoSuchRevision if
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
516
        the tree is not locally available, even if they could obtain the
517
        tree via a repository or some other means. Callers are responsible
1908.11.1 by Robert Collins
Add a new method ``Tree.revision_tree`` which allows access to cached
518
        for finding the ultimate source for a revision tree.
519
520
        :param revision_id: The revision_id of the requested tree.
521
        :return: A Tree.
522
        :raises: NoSuchRevision if the tree cannot be obtained.
523
        """
524
        raise errors.NoSuchRevisionInTree(self, revision_id)
525
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
526
    def unknowns(self):
527
        """What files are present in this tree and unknown.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
528
1773.2.1 by Robert Collins
Teach all trees about unknowns, conflicts and get_parent_ids.
529
        :return: an iterator over the unknown files.
530
        """
531
        return iter([])
532
1543.1.1 by Denys Duchier
lock operations for trees - use them for diff
533
    def unlock(self):
534
        pass
1658.1.9 by Martin Pool
Give an error for bzr diff on an nonexistent file (Malone #3619)
535
536
    def filter_unversioned_files(self, paths):
2255.7.62 by Robert Collins
Update the Tree.filter_unversioned_files docstring to reflect what the existing implementations actually do, and change the WorkingTree4 implementation to match a newly created test for it.
537
        """Filter out paths that are versioned.
1658.1.9 by Martin Pool
Give an error for bzr diff on an nonexistent file (Malone #3619)
538
539
        :return: set of paths.
540
        """
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
541
        raise NotImplementedError(self.filter_unversioned_files)
1852.7.1 by Robert Collins
Move RevisionTree out of tree.py.
542
1852.15.3 by Robert Collins
Add a first-cut Tree.walkdirs method.
543
    def walkdirs(self, prefix=""):
544
        """Walk the contents of this tree from path down.
545
546
        This yields all the data about the contents of a directory at a time.
547
        After each directory has been yielded, if the caller has mutated the
548
        list to exclude some directories, they are then not descended into.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
549
1852.15.3 by Robert Collins
Add a first-cut Tree.walkdirs method.
550
        The data yielded is of the form:
1852.15.7 by Robert Collins
Start testing behaviour of unknowns in WorkingTree.walkdirs.
551
        ((directory-relpath, directory-path-from-root, directory-fileid),
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
552
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id,
1852.15.7 by Robert Collins
Start testing behaviour of unknowns in WorkingTree.walkdirs.
553
          versioned_kind), ...]),
554
         - directory-relpath is the containing dirs relpath from prefix
555
         - directory-path-from-root is the containing dirs path from /
556
         - directory-fileid is the id of the directory if it is versioned.
1852.15.3 by Robert Collins
Add a first-cut Tree.walkdirs method.
557
         - relpath is the relative path within the subtree being walked.
558
         - basename is the basename
559
         - kind is the kind of the file now. If unknonwn then the file is not
560
           present within the tree - but it may be recorded as versioned. See
561
           versioned_kind.
562
         - lstat is the stat data *if* the file was statted.
563
         - path_from_tree_root is the path from the root of the tree.
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
564
         - file_id is the file_id if the entry is versioned.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
565
         - versioned_kind is the kind of the file as last recorded in the
1852.15.3 by Robert Collins
Add a first-cut Tree.walkdirs method.
566
           versioning system. If 'unknown' the file is not versioned.
567
        One of 'kind' and 'versioned_kind' must not be 'unknown'.
568
569
        :param prefix: Start walking from prefix within the tree rather than
570
        at the root. This allows one to walk a subtree but get paths that are
571
        relative to a tree rooted higher up.
572
        :return: an iterator over the directory data.
573
        """
574
        raise NotImplementedError(self.walkdirs)
575
3368.2.45 by Ian Clatworthy
add and use supports_content_filtering API
576
    def supports_content_filtering(self):
577
        return False
578
3368.2.5 by Ian Clatworthy
incorporate jameinel's review feedback
579
    def _content_filter_stack(self, path=None, file_id=None):
3368.2.45 by Ian Clatworthy
add and use supports_content_filtering API
580
        """The stack of content filters for a path if filtering is supported.
3368.2.47 by Ian Clatworthy
merge bzr.dev r4042
581
3368.2.4 by Ian Clatworthy
make content filter lookup a tree responsibility
582
        Readers will be applied in first-to-last order.
583
        Writers will be applied in last-to-first order.
3368.2.5 by Ian Clatworthy
incorporate jameinel's review feedback
584
        Either the path or the file-id needs to be provided.
585
586
        :param path: path relative to the root of the tree
587
            or None if unknown
588
        :param file_id: file_id or None if unknown
589
        :return: the list of filters - [] if there are none
3368.2.4 by Ian Clatworthy
make content filter lookup a tree responsibility
590
        """
3368.2.16 by Ian Clatworthy
add real implementation of Tree.get_filter_stack
591
        filter_pref_names = filters._get_registered_names()
592
        if len(filter_pref_names) == 0:
593
            return []
594
        if path is None:
595
            path = self.id2path(file_id)
3368.2.29 by Ian Clatworthy
access rules via get_special_file to fix recursion bug
596
        prefs = self.iter_search_rules([path], filter_pref_names).next()
3368.2.30 by Ian Clatworthy
add -Dfilters support
597
        stk = filters._get_filter_stack_for(prefs)
598
        if 'filters' in debug.debug_flags:
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
599
            trace.note("*** %s content-filter: %s => %r" % (path,prefs,stk))
3368.2.30 by Ian Clatworthy
add -Dfilters support
600
        return stk
3368.2.4 by Ian Clatworthy
make content filter lookup a tree responsibility
601
3368.2.45 by Ian Clatworthy
add and use supports_content_filtering API
602
    def _content_filter_stack_provider(self):
603
        """A function that returns a stack of ContentFilters.
604
605
        The function takes a path (relative to the top of the tree) and a
606
        file-id as parameters.
607
608
        :return: None if content filtering is not supported by this tree.
609
        """
610
        if self.supports_content_filtering():
611
            return lambda path, file_id: \
612
                    self._content_filter_stack(path, file_id)
613
        else:
614
            return None
615
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
616
    def iter_search_rules(self, path_names, pref_names=None,
4324.4.1 by Marius Kruger
Make it possible to blackboxtest rules
617
        _default_searcher=None):
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
618
        """Find the preferences for filenames in a tree.
619
620
        :param path_names: an iterable of paths to find attributes for.
621
          Paths are given relative to the root of the tree.
622
        :param pref_names: the list of preferences to lookup - None for all
623
        :param _default_searcher: private parameter to assist testing - don't use
624
        :return: an iterator of tuple sequences, one per path-name.
625
          See _RulesSearcher.get_items for details on the tuple sequence.
626
        """
4324.4.1 by Marius Kruger
Make it possible to blackboxtest rules
627
        if _default_searcher is None:
628
            _default_searcher = rules._per_user_searcher
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
629
        searcher = self._get_rules_searcher(_default_searcher)
630
        if searcher is not None:
3398.1.34 by Ian Clatworthy
changed API design as requested by jam during review
631
            if pref_names is not None:
632
                for path in path_names:
633
                    yield searcher.get_selected_items(path, pref_names)
634
            else:
635
                for path in path_names:
636
                    yield searcher.get_items(path)
3398.1.24 by Ian Clatworthy
make iter_search_rules a tree method
637
638
    def _get_rules_searcher(self, default_searcher):
639
        """Get the RulesSearcher for this tree given the default one."""
640
        searcher = default_searcher
641
        return searcher
642
1852.7.1 by Robert Collins
Move RevisionTree out of tree.py.
643
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
644
class InventoryTree(Tree):
645
    """A tree that relies on an inventory for its metadata.
646
647
    Trees contain an `Inventory` object, and also know how to retrieve
648
    file texts mentioned in the inventory, either from a working
649
    directory or from a store.
650
651
    It is possible for trees to contain files that are not described
652
    in their inventory or vice versa; for this use `filenames()`.
5777.3.5 by Jelmer Vernooij
Add note about _inventory.
653
654
    Subclasses should set the _inventory attribute, which is considered
655
    private to external API users.
5777.3.1 by Jelmer Vernooij
Split InventoryTree out of Tree.
656
    """
657
658
    def get_canonical_inventory_paths(self, paths):
659
        """Like get_canonical_inventory_path() but works on multiple items.
660
661
        :param paths: A sequence of paths relative to the root of the tree.
662
        :return: A list of paths, with each item the corresponding input path
663
        adjusted to account for existing elements that match case
664
        insensitively.
665
        """
666
        return list(self._yield_canonical_inventory_paths(paths))
667
668
    def get_canonical_inventory_path(self, path):
669
        """Returns the first inventory item that case-insensitively matches path.
670
671
        If a path matches exactly, it is returned. If no path matches exactly
672
        but more than one path matches case-insensitively, it is implementation
673
        defined which is returned.
674
675
        If no path matches case-insensitively, the input path is returned, but
676
        with as many path entries that do exist changed to their canonical
677
        form.
678
679
        If you need to resolve many names from the same tree, you should
680
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
681
682
        :param path: A paths relative to the root of the tree.
683
        :return: The input path adjusted to account for existing elements
684
        that match case insensitively.
685
        """
686
        return self._yield_canonical_inventory_paths([path]).next()
687
688
    def _yield_canonical_inventory_paths(self, paths):
689
        for path in paths:
690
            # First, if the path as specified exists exactly, just use it.
691
            if self.path2id(path) is not None:
692
                yield path
693
                continue
694
            # go walkin...
695
            cur_id = self.get_root_id()
696
            cur_path = ''
697
            bit_iter = iter(path.split("/"))
698
            for elt in bit_iter:
699
                lelt = elt.lower()
700
                new_path = None
701
                for child in self.iter_children(cur_id):
702
                    try:
703
                        # XXX: it seem like if the child is known to be in the
704
                        # tree, we shouldn't need to go from its id back to
705
                        # its path -- mbp 2010-02-11
706
                        #
707
                        # XXX: it seems like we could be more efficient
708
                        # by just directly looking up the original name and
709
                        # only then searching all children; also by not
710
                        # chopping paths so much. -- mbp 2010-02-11
711
                        child_base = os.path.basename(self.id2path(child))
712
                        if (child_base == elt):
713
                            # if we found an exact match, we can stop now; if
714
                            # we found an approximate match we need to keep
715
                            # searching because there might be an exact match
716
                            # later.  
717
                            cur_id = child
718
                            new_path = osutils.pathjoin(cur_path, child_base)
719
                            break
720
                        elif child_base.lower() == lelt:
721
                            cur_id = child
722
                            new_path = osutils.pathjoin(cur_path, child_base)
723
                    except errors.NoSuchId:
724
                        # before a change is committed we can see this error...
725
                        continue
726
                if new_path:
727
                    cur_path = new_path
728
                else:
729
                    # got to the end of this directory and no entries matched.
730
                    # Return what matched so far, plus the rest as specified.
731
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
732
                    break
733
            yield cur_path
734
        # all done.
735
736
    def _get_inventory(self):
737
        return self._inventory
738
739
    inventory = property(_get_inventory,
740
                         doc="Inventory of this Tree")
741
742
    @needs_read_lock
743
    def path2id(self, path):
744
        """Return the id for path in this tree."""
745
        return self._inventory.path2id(path)
746
747
    def id2path(self, file_id):
748
        """Return the path for a file id.
749
750
        :raises NoSuchId:
751
        """
752
        return self.inventory.id2path(file_id)
753
754
    def has_id(self, file_id):
755
        return self.inventory.has_id(file_id)
756
757
    def has_or_had_id(self, file_id):
758
        return self.inventory.has_id(file_id)
759
760
    def __iter__(self):
761
        return iter(self.inventory)
762
763
    def filter_unversioned_files(self, paths):
764
        """Filter out paths that are versioned.
765
766
        :return: set of paths.
767
        """
768
        # NB: we specifically *don't* call self.has_filename, because for
769
        # WorkingTrees that can indicate files that exist on disk but that
770
        # are not versioned.
771
        pred = self.inventory.has_filename
772
        return set((p for p in paths if not pred(p)))
773
774
    @needs_read_lock
775
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
776
        """Walk the tree in 'by_dir' order.
777
778
        This will yield each entry in the tree as a (path, entry) tuple.
779
        The order that they are yielded is:
780
781
        See Tree.iter_entries_by_dir for details.
782
783
        :param yield_parents: If True, yield the parents from the root leading
784
            down to specific_file_ids that have been requested. This has no
785
            impact if specific_file_ids is None.
786
        """
787
        return self.inventory.iter_entries_by_dir(
788
            specific_file_ids=specific_file_ids, yield_parents=yield_parents)
789
790
    def get_file_by_path(self, path):
791
        return self.get_file(self._inventory.path2id(path), path)
792
793
1 by mbp at sourcefrog
import from baz patch-364
794
######################################################################
795
# diff
796
797
# TODO: Merge these two functions into a single one that can operate
798
# on either a whole tree or a set of files.
799
800
# TODO: Return the diff in order by filename, not by category or in
801
# random order.  Can probably be done by lock-stepping through the
802
# filenames from both trees.
803
804
805
def file_status(filename, old_tree, new_tree):
806
    """Return single-letter status, old and new names for a file.
807
808
    The complexity here is in deciding how to represent renames;
809
    many complex cases are possible.
810
    """
811
    old_inv = old_tree.inventory
812
    new_inv = new_tree.inventory
813
    new_id = new_inv.path2id(filename)
814
    old_id = old_inv.path2id(filename)
815
816
    if not new_id and not old_id:
817
        # easy: doesn't exist in either; not versioned at all
818
        if new_tree.is_ignored(filename):
819
            return 'I', None, None
820
        else:
821
            return '?', None, None
822
    elif new_id:
823
        # There is now a file of this name, great.
824
        pass
825
    else:
826
        # There is no longer a file of this name, but we can describe
827
        # what happened to the file that used to have
828
        # this name.  There are two possibilities: either it was
829
        # deleted entirely, or renamed.
830
        if new_inv.has_id(old_id):
831
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
832
        else:
833
            return 'D', old_inv.id2path(old_id), None
834
835
    # if the file_id is new in this revision, it is added
836
    if new_id and not old_inv.has_id(new_id):
837
        return 'A'
838
839
    # if there used to be a file of this name, but that ID has now
840
    # disappeared, it is deleted
841
    if old_id and not new_inv.has_id(old_id):
842
        return 'D'
843
844
    return 'wtf?'
845
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
846
1551.7.22 by Aaron Bentley
Changes from review
847
def find_ids_across_trees(filenames, trees, require_versioned=True):
848
    """Find the ids corresponding to specified filenames.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
849
1551.7.22 by Aaron Bentley
Changes from review
850
    All matches in all trees will be used, and all children of matched
851
    directories will be used.
852
1551.10.7 by Aaron Bentley
Use new-style output for status
853
    :param filenames: The filenames to find file_ids for (if None, returns
854
        None)
1551.7.22 by Aaron Bentley
Changes from review
855
    :param trees: The trees to find file_ids within
856
    :param require_versioned: if true, all specified filenames must occur in
857
    at least one tree.
858
    :return: a set of file ids for the specified filenames and their children.
859
    """
3363.12.9 by Aaron Bentley
Revert changed select-all test
860
    if not filenames:
1551.7.22 by Aaron Bentley
Changes from review
861
        return None
2255.2.82 by Robert Collins
various notes about find_ids_across_trees
862
    specified_path_ids = _find_ids_across_trees(filenames, trees,
863
        require_versioned)
864
    return _find_children_across_trees(specified_path_ids, trees)
865
866
867
def _find_ids_across_trees(filenames, trees, require_versioned):
1551.7.22 by Aaron Bentley
Changes from review
868
    """Find the ids corresponding to specified filenames.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
869
2255.2.82 by Robert Collins
various notes about find_ids_across_trees
870
    All matches in all trees will be used, but subdirectories are not scanned.
1551.7.22 by Aaron Bentley
Changes from review
871
1551.7.14 by Aaron Bentley
Use specified_file_ids instead of is_inside_any in compare_trees
872
    :param filenames: The filenames to find file_ids for
873
    :param trees: The trees to find file_ids within
1551.7.16 by Aaron Bentley
Fix docs
874
    :param require_versioned: if true, all specified filenames must occur in
2255.2.82 by Robert Collins
various notes about find_ids_across_trees
875
        at least one tree.
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
876
    :return: a set of file ids for the specified filenames
1551.7.14 by Aaron Bentley
Use specified_file_ids instead of is_inside_any in compare_trees
877
    """
1551.7.17 by Aaron Bentley
Switch to PathsNotVersioned, accept extra_trees
878
    not_versioned = []
1551.7.18 by Aaron Bentley
Indentation and documentation fixes
879
    interesting_ids = set()
880
    for tree_path in filenames:
881
        not_found = True
882
        for tree in trees:
2255.2.82 by Robert Collins
various notes about find_ids_across_trees
883
            file_id = tree.path2id(tree_path)
1551.7.18 by Aaron Bentley
Indentation and documentation fixes
884
            if file_id is not None:
885
                interesting_ids.add(file_id)
886
                not_found = False
887
        if not_found:
888
            not_versioned.append(tree_path)
1551.7.22 by Aaron Bentley
Changes from review
889
    if len(not_versioned) > 0 and require_versioned:
890
        raise errors.PathsNotVersionedError(not_versioned)
891
    return interesting_ids
892
893
894
def _find_children_across_trees(specified_ids, trees):
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
895
    """Return a set including specified ids and their children.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
896
1551.7.22 by Aaron Bentley
Changes from review
897
    All matches in all trees will be used.
898
899
    :param trees: The trees to find file_ids within
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
900
    :return: a set containing all specified ids and their children
1551.7.22 by Aaron Bentley
Changes from review
901
    """
902
    interesting_ids = set(specified_ids)
1551.7.18 by Aaron Bentley
Indentation and documentation fixes
903
    pending = interesting_ids
904
    # now handle children of interesting ids
905
    # we loop so that we handle all children of each id in both trees
906
    while len(pending) > 0:
907
        new_pending = set()
908
        for file_id in pending:
1551.7.14 by Aaron Bentley
Use specified_file_ids instead of is_inside_any in compare_trees
909
            for tree in trees:
4544.2.1 by Robert Collins
Add interface enforcement for the behaviour of iter_changes with missing subtrees with explicit paths - the whole subtree is returned.
910
                if not tree.has_or_had_id(file_id):
1551.7.18 by Aaron Bentley
Indentation and documentation fixes
911
                    continue
3363.12.2 by Aaron Bentley
Implement tree.iter_children to instead of adjusting InventoryEntry handling
912
                for child_id in tree.iter_children(file_id):
913
                    if child_id not in interesting_ids:
914
                        new_pending.add(child_id)
1551.7.18 by Aaron Bentley
Indentation and documentation fixes
915
        interesting_ids.update(new_pending)
916
        pending = new_pending
1551.7.14 by Aaron Bentley
Use specified_file_ids instead of is_inside_any in compare_trees
917
    return interesting_ids
1852.8.2 by Robert Collins
Add InterTree class to represent InterTree operations.
918
919
920
class InterTree(InterObject):
921
    """This class represents operations taking place between two Trees.
922
923
    Its instances have methods like 'compare' and contain references to the
924
    source and target trees these operations are to be carried out on.
925
2818.2.1 by Ian Clatworthy
minor tree & dirstate code cleanups
926
    Clients of bzrlib should not need to use InterTree directly, rather they
1852.8.2 by Robert Collins
Add InterTree class to represent InterTree operations.
927
    should use the convenience methods on Tree such as 'Tree.compare()' which
928
    will pass through to InterTree as appropriate.
929
    """
930
4585.1.18 by Jelmer Vernooij
Add note saying that InterTree will not be tested if the from and to formats are not set.
931
    # Formats that will be used to test this InterTree. If both are
932
    # None, this InterTree will not be tested (e.g. because a complex
933
    # setup is required)
934
    _matching_from_tree_format = None
935
    _matching_to_tree_format = None
936
1910.2.15 by Aaron Bentley
Back out inter.get changes, make optimizers an ordered list
937
    _optimisers = []
1852.8.2 by Robert Collins
Add InterTree class to represent InterTree operations.
938
5837.1.2 by Jelmer Vernooij
Register defaults as first optimiser for existing Inter objects.
939
    @classmethod
940
    def is_compatible(kls, source, target):
941
        # The default implementation is naive and uses the public API, so
942
        # it works for all trees.
943
        return True
944
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
945
    def _changes_from_entries(self, source_entry, target_entry,
946
        source_path=None, target_path=None):
947
        """Generate a iter_changes tuple between source_entry and target_entry.
948
949
        :param source_entry: An inventory entry from self.source, or None.
950
        :param target_entry: An inventory entry from self.target, or None.
951
        :param source_path: The path of source_entry, if known. If not known
952
            it will be looked up.
953
        :param target_path: The path of target_entry, if known. If not known
954
            it will be looked up.
955
        :return: A tuple, item 0 of which is an iter_changes result tuple, and
956
            item 1 is True if there are any changes in the result tuple.
957
        """
958
        if source_entry is None:
959
            if target_entry is None:
960
                return None
961
            file_id = target_entry.file_id
962
        else:
963
            file_id = source_entry.file_id
964
        if source_entry is not None:
965
            source_versioned = True
966
            source_name = source_entry.name
967
            source_parent = source_entry.parent_id
968
            if source_path is None:
969
                source_path = self.source.id2path(file_id)
970
            source_kind, source_executable, source_stat = \
971
                self.source._comparison_data(source_entry, source_path)
972
        else:
973
            source_versioned = False
974
            source_name = None
975
            source_parent = None
976
            source_kind = None
977
            source_executable = None
978
        if target_entry is not None:
979
            target_versioned = True
980
            target_name = target_entry.name
981
            target_parent = target_entry.parent_id
982
            if target_path is None:
983
                target_path = self.target.id2path(file_id)
984
            target_kind, target_executable, target_stat = \
985
                self.target._comparison_data(target_entry, target_path)
986
        else:
987
            target_versioned = False
988
            target_name = None
989
            target_parent = None
990
            target_kind = None
991
            target_executable = None
992
        versioned = (source_versioned, target_versioned)
993
        kind = (source_kind, target_kind)
994
        changed_content = False
995
        if source_kind != target_kind:
996
            changed_content = True
997
        elif source_kind == 'file':
998
            if (self.source.get_file_sha1(file_id, source_path, source_stat) !=
999
                self.target.get_file_sha1(file_id, target_path, target_stat)):
1000
                changed_content = True
1001
        elif source_kind == 'symlink':
1002
            if (self.source.get_symlink_target(file_id) !=
1003
                self.target.get_symlink_target(file_id)):
1004
                changed_content = True
1005
            # XXX: Yes, the indentation below is wrong. But fixing it broke
1006
            # test_merge.TestMergerEntriesLCAOnDisk.
1007
            # test_nested_tree_subtree_renamed_and_modified. We'll wait for
1008
            # the fix from bzr.dev -- vila 2009026
1009
            elif source_kind == 'tree-reference':
1010
                if (self.source.get_reference_revision(file_id, source_path)
1011
                    != self.target.get_reference_revision(file_id, target_path)):
1012
                    changed_content = True
1013
        parent = (source_parent, target_parent)
1014
        name = (source_name, target_name)
1015
        executable = (source_executable, target_executable)
1016
        if (changed_content is not False or versioned[0] != versioned[1]
1017
            or parent[0] != parent[1] or name[0] != name[1] or
1018
            executable[0] != executable[1]):
1019
            changes = True
1020
        else:
1021
            changes = False
1022
        return (file_id, (source_path, target_path), changed_content,
1023
                versioned, parent, name, kind, executable), changes
1024
1852.11.1 by Robert Collins
Deprecate compare_trees and move its body to InterTree.changes_from.
1025
    @needs_read_lock
1852.9.4 by Robert Collins
Add minimal test for Tree.compare(extra_trees=...).
1026
    def compare(self, want_unchanged=False, specific_files=None,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1027
        extra_trees=None, require_versioned=False, include_root=False,
1028
        want_unversioned=False):
1852.9.3 by Robert Collins
Convert the test_delta tests to intertree_implementation and workingtree_implementation tests as appropriate.
1029
        """Return the changes from source to target.
1852.8.3 by Robert Collins
Implement an InterTreeTestProvider and a trivial test_compare test case.
1030
1031
        :return: A TreeDelta.
1852.9.4 by Robert Collins
Add minimal test for Tree.compare(extra_trees=...).
1032
        :param specific_files: An optional list of file paths to restrict the
1033
            comparison to. When mapping filenames to ids, all matches in all
1034
            trees (including optional extra_trees) are used, and all children of
1035
            matched directories are included.
1036
        :param want_unchanged: An optional boolean requesting the inclusion of
1037
            unchanged entries in the result.
1038
        :param extra_trees: An optional list of additional trees to use when
1039
            mapping the contents of specific_files (paths) to file_ids.
1852.9.5 by Robert Collins
Add tests for require_versioned to the InterTree.compare() test suite.
1040
        :param require_versioned: An optional boolean (defaults to False). When
1041
            supplied and True all the 'specific_files' must be versioned, or
1042
            a PathsNotVersionedError will be thrown.
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1043
        :param want_unversioned: Scan for unversioned paths.
1852.8.3 by Robert Collins
Implement an InterTreeTestProvider and a trivial test_compare test case.
1044
        """
2255.2.105 by Robert Collins
Unfuck InterTree.compare which I broke with the paths2ids implementation.
1045
        trees = (self.source,)
1852.11.1 by Robert Collins
Deprecate compare_trees and move its body to InterTree.changes_from.
1046
        if extra_trees is not None:
1047
            trees = trees + tuple(extra_trees)
2255.2.102 by Robert Collins
Use Tree.path2ids in status operations.
1048
        # target is usually the newer tree:
2255.2.105 by Robert Collins
Unfuck InterTree.compare which I broke with the paths2ids implementation.
1049
        specific_file_ids = self.target.paths2ids(specific_files, trees,
2255.2.102 by Robert Collins
Use Tree.path2ids in status operations.
1050
            require_versioned=require_versioned)
1852.11.1 by Robert Collins
Deprecate compare_trees and move its body to InterTree.changes_from.
1051
        if specific_files and not specific_file_ids:
1052
            # All files are unversioned, so just return an empty delta
1053
            # _compare_trees would think we want a complete delta
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1054
            result = delta.TreeDelta()
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
1055
            fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
2255.7.91 by Robert Collins
Move unknown detection in long status into the delta creation, saving a tree-scan.
1056
            result.unversioned = [(path, None,
1057
                self.target._comparison_data(fake_entry, path)[0]) for path in
1058
                specific_files]
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1059
            return result
1852.11.1 by Robert Collins
Deprecate compare_trees and move its body to InterTree.changes_from.
1060
        return delta._compare_trees(self.source, self.target, want_unchanged,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1061
            specific_files, include_root, extra_trees=extra_trees,
2655.2.1 by Marius Kruger
InterTree.compare and delta._compare_trees did not pass its
1062
            require_versioned=require_versioned,
2255.7.90 by Robert Collins
Add unversioned path reporting to TreeDelta.
1063
            want_unversioned=want_unversioned)
2012.1.1 by Aaron Bentley
Implement change iterator
1064
3254.1.1 by Aaron Bentley
Make Tree.iter_changes a public method
1065
    def iter_changes(self, include_unchanged=False,
2255.2.149 by Robert Collins
Crufty but existing _iter_changes implementation for WorkingTreeFormat4.
1066
                      specific_files=None, pb=None, extra_trees=[],
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1067
                      require_versioned=True, want_unversioned=False):
2012.1.1 by Aaron Bentley
Implement change iterator
1068
        """Generate an iterator of changes between trees.
1069
1070
        A tuple is returned:
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1071
        (file_id, (path_in_source, path_in_target),
1072
         changed_content, versioned, parent, name, kind,
2012.1.1 by Aaron Bentley
Implement change iterator
1073
         executable)
1074
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1075
        Changed_content is True if the file's content has changed.  This
1076
        includes changes to its kind, and to a symlink's target.
2012.1.1 by Aaron Bentley
Implement change iterator
1077
2012.1.15 by Aaron Bentley
Minor tweaks
1078
        versioned, parent, name, kind, executable are tuples of (from, to).
1079
        If a file is missing in a tree, its kind is None.
2012.1.1 by Aaron Bentley
Implement change iterator
1080
2255.2.122 by Robert Collins
Alter intertree implementation tests to let dirstate inter-trees be correctly parameterised.
1081
        Iteration is done in parent-to-child order, relative to the target
1082
        tree.
2255.2.149 by Robert Collins
Crufty but existing _iter_changes implementation for WorkingTreeFormat4.
1083
1084
        There is no guarantee that all paths are in sorted order: the
1085
        requirement to expand the search due to renames may result in children
1086
        that should be found early being found late in the search, after
1087
        lexically later results have been returned.
1088
        :param require_versioned: Raise errors.PathsNotVersionedError if a
1089
            path in the specific_files list is not versioned in one of
1090
            source, target or extra_trees.
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1091
        :param specific_files: An optional list of file paths to restrict the
1092
            comparison to. When mapping filenames to ids, all matches in all
1093
            trees (including optional extra_trees) are used, and all children
1094
            of matched directories are included. The parents in the target tree
1095
            of the specific files up to and including the root of the tree are
1096
            always evaluated for changes too.
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1097
        :param want_unversioned: Should unversioned files be returned in the
1098
            output. An unversioned file is defined as one with (False, False)
1099
            for the versioned pair.
2012.1.1 by Aaron Bentley
Implement change iterator
1100
        """
2255.2.149 by Robert Collins
Crufty but existing _iter_changes implementation for WorkingTreeFormat4.
1101
        lookup_trees = [self.source]
1102
        if extra_trees:
1103
             lookup_trees.extend(extra_trees)
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1104
        # The ids of items we need to examine to insure delta consistency.
1105
        precise_file_ids = set()
1106
        changed_file_ids = []
2748.3.1 by Aaron Bentley
Start supporting [] for empty list
1107
        if specific_files == []:
1108
            specific_file_ids = []
1109
        else:
1110
            specific_file_ids = self.target.paths2ids(specific_files,
1111
                lookup_trees, require_versioned=require_versioned)
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1112
        if specific_files is not None:
1113
            # reparented or added entries must have their parents included
1114
            # so that valid deltas can be created. The seen_parents set
1115
            # tracks the parents that we need to have.
1116
            # The seen_dirs set tracks directory entries we've yielded.
1117
            # After outputting version object in to_entries we set difference
1118
            # the two seen sets and start checking parents.
1119
            seen_parents = set()
1120
            seen_dirs = set()
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1121
        if want_unversioned:
2748.3.1 by Aaron Bentley
Start supporting [] for empty list
1122
            all_unversioned = sorted([(p.split('/'), p) for p in
1123
                                     self.target.extras()
1124
                if specific_files is None or
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1125
                    osutils.is_inside_any(specific_files, p)])
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
1126
            all_unversioned = collections.deque(all_unversioned)
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1127
        else:
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
1128
            all_unversioned = collections.deque()
2012.1.1 by Aaron Bentley
Implement change iterator
1129
        to_paths = {}
3363.14.2 by Aaron Bentley
Get iter_changes running to completion
1130
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
1551.9.29 by Aaron Bentley
Optimize Tree._iter_changes with specific file_ids
1131
            specific_file_ids=specific_file_ids))
2012.1.16 by Aaron Bentley
Support progress bars in iter_changes
1132
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
3363.14.2 by Aaron Bentley
Get iter_changes running to completion
1133
        to_entries_by_dir = list(self.target.iter_entries_by_dir(
1551.9.31 by Aaron Bentley
Handle to_paths correctly when parent of file is not in specified_ids
1134
            specific_file_ids=specific_file_ids))
1551.9.29 by Aaron Bentley
Optimize Tree._iter_changes with specific file_ids
1135
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
2012.1.16 by Aaron Bentley
Support progress bars in iter_changes
1136
        entry_count = 0
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1137
        # the unversioned path lookup only occurs on real trees - where there
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1138
        # can be extras. So the fake_entry is solely used to look up
1139
        # executable it values when execute is not supported.
5745.3.4 by Jelmer Vernooij
Merge bzr.dev.
1140
        fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1141
        for target_path, target_entry in to_entries_by_dir:
1142
            while (all_unversioned and
1143
                all_unversioned[0][0] < target_path.split('/')):
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1144
                unversioned_path = all_unversioned.popleft()
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1145
                target_kind, target_executable, target_stat = \
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1146
                    self.target._comparison_data(fake_entry, unversioned_path[1])
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1147
                yield (None, (None, unversioned_path[1]), True, (False, False),
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1148
                    (None, None),
1149
                    (None, unversioned_path[0][-1]),
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1150
                    (None, target_kind),
1151
                    (None, target_executable))
1152
            source_path, source_entry = from_data.get(target_entry.file_id,
1153
                (None, None))
1154
            result, changes = self._changes_from_entries(source_entry,
1155
                target_entry, source_path=source_path, target_path=target_path)
1156
            to_paths[result[0]] = result[1][1]
2012.1.16 by Aaron Bentley
Support progress bars in iter_changes
1157
            entry_count += 1
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1158
            if result[3][0]:
1551.9.29 by Aaron Bentley
Optimize Tree._iter_changes with specific file_ids
1159
                entry_count += 1
2012.1.16 by Aaron Bentley
Support progress bars in iter_changes
1160
            if pb is not None:
1161
                pb.update('comparing files', entry_count, num_entries)
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1162
            if changes or include_unchanged:
1163
                if specific_file_ids is not None:
1164
                    new_parent_id = result[4][1]
1165
                    precise_file_ids.add(new_parent_id)
1166
                    changed_file_ids.append(result[0])
1167
                yield result
1168
            # Ensure correct behaviour for reparented/added specific files.
1169
            if specific_files is not None:
1170
                # Record output dirs
1171
                if result[6][1] == 'directory':
1172
                    seen_dirs.add(result[0])
1173
                # Record parents of reparented/added entries.
1174
                versioned = result[3]
1175
                parents = result[4]
1176
                if not versioned[0] or parents[0] != parents[1]:
1177
                    seen_parents.add(parents[1])
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1178
        while all_unversioned:
1179
            # yield any trailing unversioned paths
1180
            unversioned_path = all_unversioned.popleft()
1181
            to_kind, to_executable, to_stat = \
1182
                self.target._comparison_data(fake_entry, unversioned_path[1])
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1183
            yield (None, (None, unversioned_path[1]), True, (False, False),
2255.7.85 by Robert Collins
Teach _iter_changes to gather unversioned path details upon request.
1184
                (None, None),
1185
                (None, unversioned_path[0][-1]),
1186
                (None, to_kind),
1187
                (None, to_executable))
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1188
        # Yield all remaining source paths
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
1189
        for path, from_entry in from_entries_by_dir:
2012.1.1 by Aaron Bentley
Implement change iterator
1190
            file_id = from_entry.file_id
1191
            if file_id in to_paths:
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1192
                # already returned
2012.1.1 by Aaron Bentley
Implement change iterator
1193
                continue
5390.3.3 by Andrew Bennetts
Use has_id rather than __contains__; expand NEWS entry; add What's New entry.
1194
            if not self.target.has_id(file_id):
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1195
                # common case - paths we have not emitted are not present in
1196
                # target.
1197
                to_path = None
1198
            else:
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1199
                to_path = self.target.id2path(file_id)
2012.1.16 by Aaron Bentley
Support progress bars in iter_changes
1200
            entry_count += 1
1201
            if pb is not None:
1202
                pb.update('comparing files', entry_count, num_entries)
2012.1.1 by Aaron Bentley
Implement change iterator
1203
            versioned = (True, False)
1204
            parent = (from_entry.parent_id, None)
1205
            name = (from_entry.name, None)
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
1206
            from_kind, from_executable, stat_value = \
2255.2.122 by Robert Collins
Alter intertree implementation tests to let dirstate inter-trees be correctly parameterised.
1207
                self.source._comparison_data(from_entry, path)
2012.1.7 by Aaron Bentley
Get tree._iter_changed down to ~ 1 stat per file
1208
            kind = (from_kind, None)
2012.1.2 by Aaron Bentley
reimplement compare_trees
1209
            executable = (from_executable, None)
3619.4.1 by Robert Collins
Improve tests for the behaviour of Tree.iter_changes for missing paths that are only present in one tree, and fix found bugs. (Robert Collins)
1210
            changed_content = from_kind is not None
2012.1.1 by Aaron Bentley
Implement change iterator
1211
            # the parent's path is necessarily known at this point.
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1212
            changed_file_ids.append(file_id)
2255.7.96 by Robert Collins
Change _iter_changes interface to yield both old and new paths.
1213
            yield(file_id, (path, to_path), changed_content, versioned, parent,
2012.1.1 by Aaron Bentley
Implement change iterator
1214
                  name, kind, executable)
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1215
        changed_file_ids = set(changed_file_ids)
1216
        if specific_file_ids is not None:
1217
            for result in self._handle_precise_ids(precise_file_ids,
1218
                changed_file_ids):
1219
                yield result
1220
1221
    def _get_entry(self, tree, file_id):
1222
        """Get an inventory entry from a tree, with missing entries as None.
1223
1224
        If the tree raises NotImplementedError on accessing .inventory, then
1225
        this is worked around using iter_entries_by_dir on just the file id
1226
        desired.
1227
1228
        :param tree: The tree to lookup the entry in.
1229
        :param file_id: The file_id to lookup.
1230
        """
1231
        try:
1232
            inventory = tree.inventory
1233
        except NotImplementedError:
1234
            # No inventory available.
1235
            try:
1236
                iterator = tree.iter_entries_by_dir(specific_file_ids=[file_id])
1237
                return iterator.next()[1]
1238
            except StopIteration:
1239
                return None
1240
        else:
1241
            try:
1242
                return inventory[file_id]
1243
            except errors.NoSuchId:
1244
                return None
1245
1246
    def _handle_precise_ids(self, precise_file_ids, changed_file_ids,
1247
        discarded_changes=None):
1248
        """Fill out a partial iter_changes to be consistent.
1249
1250
        :param precise_file_ids: The file ids of parents that were seen during
1251
            the iter_changes.
1252
        :param changed_file_ids: The file ids of already emitted items.
1253
        :param discarded_changes: An optional dict of precalculated
1254
            iter_changes items which the partial iter_changes had not output
1255
            but had calculated.
1256
        :return: A generator of iter_changes items to output.
1257
        """
1258
        # process parents of things that had changed under the users
1259
        # requested paths to prevent incorrect paths or parent ids which
1260
        # aren't in the tree.
1261
        while precise_file_ids:
1262
            precise_file_ids.discard(None)
1263
            # Don't emit file_ids twice
1264
            precise_file_ids.difference_update(changed_file_ids)
1265
            if not precise_file_ids:
1266
                break
1267
            # If the there was something at a given output path in source, we
1268
            # have to include the entry from source in the delta, or we would
1269
            # be putting this entry into a used path.
1270
            paths = []
1271
            for parent_id in precise_file_ids:
1272
                try:
1273
                    paths.append(self.target.id2path(parent_id))
1274
                except errors.NoSuchId:
1275
                    # This id has been dragged in from the source by delta
1276
                    # expansion and isn't present in target at all: we don't
1277
                    # need to check for path collisions on it.
1278
                    pass
1279
            for path in paths:
1280
                old_id = self.source.path2id(path)
1281
                precise_file_ids.add(old_id)
1282
            precise_file_ids.discard(None)
1283
            current_ids = precise_file_ids
1284
            precise_file_ids = set()
1285
            # We have to emit all of precise_file_ids that have been altered.
1286
            # We may have to output the children of some of those ids if any
1287
            # directories have stopped being directories.
1288
            for file_id in current_ids:
1289
                # Examine file_id
1290
                if discarded_changes:
1291
                    result = discarded_changes.get(file_id)
1292
                    old_entry = None
1293
                else:
1294
                    result = None
1295
                if result is None:
1296
                    old_entry = self._get_entry(self.source, file_id)
1297
                    new_entry = self._get_entry(self.target, file_id)
1298
                    result, changes = self._changes_from_entries(
1299
                        old_entry, new_entry)
1300
                else:
1301
                    changes = True
4570.2.5 by Robert Collins
Review feedback, including finding a bug with changes at the root.
1302
                # Get this parents parent to examine.
1303
                new_parent_id = result[4][1]
1304
                precise_file_ids.add(new_parent_id)
4570.2.3 by Robert Collins
Change the way iter_changes treats specific files to prevent InconsistentDeltas.
1305
                if changes:
1306
                    if (result[6][0] == 'directory' and
1307
                        result[6][1] != 'directory'):
1308
                        # This stopped being a directory, the old children have
1309
                        # to be included.
1310
                        if old_entry is None:
1311
                            # Reusing a discarded change.
1312
                            old_entry = self._get_entry(self.source, file_id)
1313
                        for child in old_entry.children.values():
1314
                            precise_file_ids.add(child.file_id)
1315
                    changed_file_ids.add(result[0])
1316
                    yield result
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1317
1318
5837.1.2 by Jelmer Vernooij
Register defaults as first optimiser for existing Inter objects.
1319
InterTree.register_optimiser(InterTree)
1320
1321
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1322
class MultiWalker(object):
1323
    """Walk multiple trees simultaneously, getting combined results."""
1324
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1325
    # Note: This could be written to not assume you can do out-of-order
1326
    #       lookups. Instead any nodes that don't match in all trees could be
1327
    #       marked as 'deferred', and then returned in the final cleanup loop.
1328
    #       For now, I think it is "nicer" to return things as close to the
1329
    #       "master_tree" order as we can.
1330
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1331
    def __init__(self, master_tree, other_trees):
1332
        """Create a new MultiWalker.
1333
1334
        All trees being walked must implement "iter_entries_by_dir()", such
1335
        that they yield (path, object) tuples, where that object will have a
1336
        '.file_id' member, that can be used to check equality.
1337
3514.3.11 by John Arbash Meinel
Cleanups suggested by Ian
1338
        :param master_tree: All trees will be 'slaved' to the master_tree such
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1339
            that nodes in master_tree will be used as 'first-pass' sync points.
1340
            Any nodes that aren't in master_tree will be merged in a second
1341
            pass.
1342
        :param other_trees: A list of other trees to walk simultaneously.
1343
        """
1344
        self._master_tree = master_tree
1345
        self._other_trees = other_trees
1346
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1347
        # Keep track of any nodes that were properly processed just out of
1348
        # order, that way we don't return them at the end, we don't have to
1349
        # track *all* processed file_ids, just the out-of-order ones
1350
        self._out_of_order_processed = set()
1351
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1352
    @staticmethod
1353
    def _step_one(iterator):
1354
        """Step an iter_entries_by_dir iterator.
1355
1356
        :return: (has_more, path, ie)
1357
            If has_more is False, path and ie will be None.
1358
        """
1359
        try:
1360
            path, ie = iterator.next()
1361
        except StopIteration:
1362
            return False, None, None
1363
        else:
1364
            return True, path, ie
1365
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1366
    @staticmethod
1367
    def _cmp_path_by_dirblock(path1, path2):
1368
        """Compare two paths based on what directory they are in.
1369
1370
        This generates a sort order, such that all children of a directory are
1371
        sorted together, and grandchildren are in the same order as the
1372
        children appear. But all grandchildren come after all children.
1373
1374
        :param path1: first path
1375
        :param path2: the second path
1376
        :return: negative number if ``path1`` comes first,
1377
            0 if paths are equal
1378
            and a positive number if ``path2`` sorts first
1379
        """
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1380
        # Shortcut this special case
1381
        if path1 == path2:
1382
            return 0
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1383
        # This is stolen from _dirstate_helpers_py.py, only switching it to
1384
        # Unicode objects. Consider using encode_utf8() and then using the
1385
        # optimized versions, or maybe writing optimized unicode versions.
1386
        if not isinstance(path1, unicode):
1387
            raise TypeError("'path1' must be a unicode string, not %s: %r"
1388
                            % (type(path1), path1))
1389
        if not isinstance(path2, unicode):
1390
            raise TypeError("'path2' must be a unicode string, not %s: %r"
1391
                            % (type(path2), path2))
3514.3.13 by John Arbash Meinel
One code path was using a tuple, another a plain path
1392
        return cmp(MultiWalker._path_to_key(path1),
1393
                   MultiWalker._path_to_key(path2))
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1394
1395
    @staticmethod
3514.3.13 by John Arbash Meinel
One code path was using a tuple, another a plain path
1396
    def _path_to_key(path):
3514.3.11 by John Arbash Meinel
Cleanups suggested by Ian
1397
        dirname, basename = osutils.split(path)
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1398
        return (dirname.split(u'/'), basename)
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1399
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1400
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
1401
        """Lookup an inventory entry by file_id.
1402
1403
        This is called when an entry is missing in the normal order.
1404
        Generally this is because a file was either renamed, or it was
1405
        deleted/added. If the entry was found in the inventory and not in
1406
        extra_entries, it will be added to self._out_of_order_processed
1407
1408
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
1409
            should be filled with entries that were found before they were
1410
            used. If file_id is present, it will be removed from the
1411
            dictionary.
1412
        :param other_tree: The Tree to search, in case we didn't find the entry
1413
            yet.
1414
        :param file_id: The file_id to look for
1415
        :return: (path, ie) if found or (None, None) if not present.
1416
        """
1417
        if file_id in extra_entries:
1418
            return extra_entries.pop(file_id)
1419
        # TODO: Is id2path better as the first call, or is
1420
        #       inventory[file_id] better as a first check?
1421
        try:
1422
            cur_path = other_tree.id2path(file_id)
1423
        except errors.NoSuchId:
1424
            cur_path = None
1425
        if cur_path is None:
1426
            return (None, None)
1427
        else:
1428
            self._out_of_order_processed.add(file_id)
1429
            cur_ie = other_tree.inventory[file_id]
1430
            return (cur_path, cur_ie)
1431
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1432
    def iter_all(self):
1433
        """Match up the values in the different trees."""
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1434
        for result in self._walk_master_tree():
1435
            yield result
1436
        self._finish_others()
1437
        for result in self._walk_others():
1438
            yield result
1439
1440
    def _walk_master_tree(self):
1441
        """First pass, walk all trees in lock-step.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1442
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1443
        When we are done, all nodes in the master_tree will have been
1444
        processed. _other_walkers, _other_entries, and _others_extra will be
1445
        set on 'self' for future processing.
1446
        """
1447
        # This iterator has the most "inlining" done, because it tends to touch
1448
        # every file in the tree, while the others only hit nodes that don't
1449
        # match.
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1450
        master_iterator = self._master_tree.iter_entries_by_dir()
1451
1452
        other_walkers = [other.iter_entries_by_dir()
1453
                         for other in self._other_trees]
1454
        other_entries = [self._step_one(walker) for walker in other_walkers]
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1455
        # Track extra nodes in the other trees
1456
        others_extra = [{} for i in xrange(len(self._other_trees))]
1457
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1458
        master_has_more = True
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1459
        step_one = self._step_one
1460
        lookup_by_file_id = self._lookup_by_file_id
1461
        out_of_order_processed = self._out_of_order_processed
1462
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1463
        while master_has_more:
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1464
            (master_has_more, path, master_ie) = step_one(master_iterator)
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1465
            if not master_has_more:
1466
                break
1467
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1468
            file_id = master_ie.file_id
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1469
            other_values = []
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1470
            other_values_append = other_values.append
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1471
            next_other_entries = []
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1472
            next_other_entries_append = next_other_entries.append
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1473
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1474
                if not other_has_more:
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1475
                    other_values_append(lookup_by_file_id(
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1476
                        others_extra[idx], self._other_trees[idx], file_id))
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1477
                    next_other_entries_append((False, None, None))
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1478
                elif file_id == other_ie.file_id:
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1479
                    # This is the critical code path, as most of the entries
1480
                    # should match between most trees.
1481
                    other_values_append((other_path, other_ie))
1482
                    next_other_entries_append(step_one(other_walkers[idx]))
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1483
                else:
1484
                    # This walker did not match, step it until it either
1485
                    # matches, or we know we are past the current walker.
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1486
                    other_walker = other_walkers[idx]
1487
                    other_extra = others_extra[idx]
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1488
                    while (other_has_more and
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1489
                           self._cmp_path_by_dirblock(other_path, path) < 0):
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1490
                        other_file_id = other_ie.file_id
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1491
                        if other_file_id not in out_of_order_processed:
1492
                            other_extra[other_file_id] = (other_path, other_ie)
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1493
                        other_has_more, other_path, other_ie = \
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1494
                            step_one(other_walker)
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1495
                    if other_has_more and other_ie.file_id == file_id:
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1496
                        # We ended up walking to this point, match and step
1497
                        # again
1498
                        other_values_append((other_path, other_ie))
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1499
                        other_has_more, other_path, other_ie = \
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1500
                            step_one(other_walker)
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1501
                    else:
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1502
                        # This record isn't in the normal order, see if it
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1503
                        # exists at all.
1504
                        other_values_append(lookup_by_file_id(
1505
                            other_extra, self._other_trees[idx], file_id))
1506
                    next_other_entries_append((other_has_more, other_path,
3514.3.2 by John Arbash Meinel
Handle the case when a record is missing in base
1507
                                               other_ie))
3514.3.1 by John Arbash Meinel
Start working on a special walker that can iterate several trees at once.
1508
            other_entries = next_other_entries
1509
1510
            # We've matched all the walkers, yield this datapoint
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1511
            yield path, file_id, master_ie, other_values
1512
        self._other_walkers = other_walkers
1513
        self._other_entries = other_entries
1514
        self._others_extra = others_extra
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1515
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1516
    def _finish_others(self):
1517
        """Finish walking the other iterators, so we get all entries."""
1518
        for idx, info in enumerate(self._other_entries):
1519
            other_extra = self._others_extra[idx]
1520
            (other_has_more, other_path, other_ie) = info
3514.3.4 by John Arbash Meinel
Handle more cases when the other tree has extra nodes.
1521
            while other_has_more:
1522
                other_file_id = other_ie.file_id
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1523
                if other_file_id not in self._out_of_order_processed:
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1524
                    other_extra[other_file_id] = (other_path, other_ie)
3514.3.4 by John Arbash Meinel
Handle more cases when the other tree has extra nodes.
1525
                other_has_more, other_path, other_ie = \
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1526
                    self._step_one(self._other_walkers[idx])
1527
        del self._other_entries
1528
1529
    def _walk_others(self):
1530
        """Finish up by walking all the 'deferred' nodes."""
1531
        # TODO: One alternative would be to grab all possible unprocessed
1532
        #       file_ids, and then sort by path, and then yield them. That
1533
        #       might ensure better ordering, in case a caller strictly
1534
        #       requires parents before children.
1535
        for idx, other_extra in enumerate(self._others_extra):
3514.3.13 by John Arbash Meinel
One code path was using a tuple, another a plain path
1536
            others = sorted(other_extra.itervalues(),
1537
                            key=lambda x: self._path_to_key(x[0]))
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1538
            for other_path, other_ie in others:
1539
                file_id = other_ie.file_id
3514.3.7 by John Arbash Meinel
comment
1540
                # We don't need to check out_of_order_processed here, because
1541
                # the lookup_by_file_id will be removing anything processed
1542
                # from the extras cache
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1543
                other_extra.pop(file_id)
3514.3.5 by John Arbash Meinel
Handle some edge cases when we have multiple other trees.
1544
                other_values = [(None, None) for i in xrange(idx)]
1545
                other_values.append((other_path, other_ie))
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1546
                for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1547
                    alt_idx = alt_idx + idx + 1
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1548
                    alt_extra = self._others_extra[alt_idx]
1549
                    alt_tree = self._other_trees[alt_idx]
3514.3.8 by John Arbash Meinel
Start trying to refactor the big function into smaller ones.
1550
                    other_values.append(self._lookup_by_file_id(
3514.3.9 by John Arbash Meinel
Refactor the large function into multiple small ones.
1551
                                            alt_extra, alt_tree, file_id))
3514.3.3 by John Arbash Meinel
Handle when the other tree has extra nodes, and we need to yield them.
1552
                yield other_path, file_id, None, other_values