~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

  • Committer: Vincent Ladeuil
  • Date: 2013-07-13 19:05:24 UTC
  • mto: This revision was merged to the branch mainline in revision 6580.
  • Revision ID: v.ladeuil+lp@free.fr-20130713190524-3bclzq4hpwkd6hkw
Urgh. pqm still runs python 2.6 so we have to maintain compatibility to land the fix 8-(

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005 Canonical Ltd
 
1
# Copyright (C) 2005-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tree classes, representing directory at point in time.
18
18
"""
19
19
 
 
20
from __future__ import absolute_import
 
21
 
20
22
import os
21
 
from collections import deque
22
 
from cStringIO import StringIO
23
 
 
24
 
import bzrlib
 
23
 
 
24
from bzrlib.lazy_import import lazy_import
 
25
lazy_import(globals(), """
 
26
import collections
 
27
 
25
28
from bzrlib import (
 
29
    conflicts as _mod_conflicts,
 
30
    debug,
26
31
    delta,
 
32
    errors,
 
33
    filters,
 
34
    inventory,
27
35
    osutils,
28
36
    revision as _mod_revision,
29
 
    conflicts as _mod_conflicts,
30
 
    symbol_versioning,
 
37
    rules,
 
38
    trace,
31
39
    )
 
40
from bzrlib.i18n import gettext
 
41
""")
 
42
 
32
43
from bzrlib.decorators import needs_read_lock
33
 
from bzrlib.errors import BzrError, BzrCheckError
34
 
from bzrlib import errors
35
 
from bzrlib.inventory import Inventory, InventoryFile
36
44
from bzrlib.inter import InterObject
37
 
from bzrlib.osutils import fingerprint_file
38
 
import bzrlib.revision
39
 
from bzrlib.trace import mutter, note
 
45
from bzrlib.symbol_versioning import (
 
46
    deprecated_in,
 
47
    deprecated_method,
 
48
    )
40
49
 
41
50
 
42
51
class Tree(object):
43
52
    """Abstract file tree.
44
53
 
45
54
    There are several subclasses:
46
 
    
 
55
 
47
56
    * `WorkingTree` exists as files on disk editable by the user.
48
57
 
49
58
    * `RevisionTree` is a tree as recorded at some point in the past.
50
59
 
51
 
    Trees contain an `Inventory` object, and also know how to retrieve
52
 
    file texts mentioned in the inventory, either from a working
53
 
    directory or from a store.
54
 
 
55
 
    It is possible for trees to contain files that are not described
56
 
    in their inventory or vice versa; for this use `filenames()`.
57
 
 
58
60
    Trees can be compared, etc, regardless of whether they are working
59
61
    trees or versioned trees.
60
62
    """
61
 
    
 
63
 
 
64
    def has_versioned_directories(self):
 
65
        """Whether this tree can contain explicitly versioned directories.
 
66
 
 
67
        This defaults to True, but some implementations may want to override
 
68
        it.
 
69
        """
 
70
        return True
 
71
 
62
72
    def changes_from(self, other, want_unchanged=False, specific_files=None,
63
73
        extra_trees=None, require_versioned=False, include_root=False,
64
74
        want_unversioned=False):
78
88
            a PathsNotVersionedError will be thrown.
79
89
        :param want_unversioned: Scan for unversioned paths.
80
90
 
81
 
        The comparison will be performed by an InterTree object looked up on 
 
91
        The comparison will be performed by an InterTree object looked up on
82
92
        self and other.
83
93
        """
84
94
        # Martin observes that Tree.changes_from returns a TreeDelta and this
93
103
            want_unversioned=want_unversioned,
94
104
            )
95
105
 
96
 
    def _iter_changes(self, from_tree, include_unchanged=False,
 
106
    def iter_changes(self, from_tree, include_unchanged=False,
97
107
                     specific_files=None, pb=None, extra_trees=None,
98
108
                     require_versioned=True, want_unversioned=False):
 
109
        """See InterTree.iter_changes"""
99
110
        intertree = InterTree.get(from_tree, self)
100
 
        return intertree._iter_changes(include_unchanged, specific_files, pb,
 
111
        return intertree.iter_changes(include_unchanged, specific_files, pb,
101
112
            extra_trees, require_versioned, want_unversioned=want_unversioned)
102
 
    
 
113
 
103
114
    def conflicts(self):
104
115
        """Get a list of the conflicts in the tree.
105
116
 
112
123
        return []
113
124
 
114
125
    def get_parent_ids(self):
115
 
        """Get the parent ids for this tree. 
 
126
        """Get the parent ids for this tree.
116
127
 
117
128
        :return: a list of parent ids. [] is returned to indicate
118
129
        a tree with no parents.
119
130
        :raises: BzrError if the parents are not known.
120
131
        """
121
132
        raise NotImplementedError(self.get_parent_ids)
122
 
    
 
133
 
123
134
    def has_filename(self, filename):
124
135
        """True if the tree has given filename."""
125
136
        raise NotImplementedError(self.has_filename)
126
137
 
127
138
    def has_id(self, file_id):
128
 
        return self.inventory.has_id(file_id)
 
139
        raise NotImplementedError(self.has_id)
129
140
 
130
 
    __contains__ = has_id
 
141
    @deprecated_method(deprecated_in((2, 4, 0)))
 
142
    def __contains__(self, file_id):
 
143
        return self.has_id(file_id)
131
144
 
132
145
    def has_or_had_id(self, file_id):
133
 
        if file_id == self.inventory.root.file_id:
134
 
            return True
135
 
        return self.inventory.has_id(file_id)
 
146
        raise NotImplementedError(self.has_or_had_id)
136
147
 
137
148
    def is_ignored(self, filename):
138
149
        """Check whether the filename is ignored by this tree.
142
153
        """
143
154
        return False
144
155
 
145
 
    def __iter__(self):
146
 
        return iter(self.inventory)
 
156
    def all_file_ids(self):
 
157
        """Iterate through all file ids, including ids for missing files."""
 
158
        raise NotImplementedError(self.all_file_ids)
147
159
 
148
160
    def id2path(self, file_id):
149
161
        """Return the path for a file id.
150
162
 
151
163
        :raises NoSuchId:
152
164
        """
153
 
        return self.inventory.id2path(file_id)
154
 
 
155
 
    def is_control_filename(self, filename):
156
 
        """True if filename is the name of a control file in this tree.
157
 
        
158
 
        :param filename: A filename within the tree. This is a relative path
159
 
        from the root of this tree.
160
 
 
161
 
        This is true IF and ONLY IF the filename is part of the meta data
162
 
        that bzr controls in this tree. I.E. a random .bzr directory placed
163
 
        on disk will not be a control file for this tree.
164
 
        """
165
 
        return self.bzrdir.is_control_filename(filename)
166
 
 
167
 
    @needs_read_lock
168
 
    def iter_entries_by_dir(self, specific_file_ids=None):
 
165
        raise NotImplementedError(self.id2path)
 
166
 
 
167
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
169
168
        """Walk the tree in 'by_dir' order.
170
169
 
171
 
        This will yield each entry in the tree as a (path, entry) tuple. The
172
 
        order that they are yielded is: the contents of a directory are 
173
 
        preceeded by the parent of a directory, and all the contents of a 
174
 
        directory are grouped together.
175
 
        """
176
 
        return self.inventory.iter_entries_by_dir(
177
 
            specific_file_ids=specific_file_ids)
 
170
        This will yield each entry in the tree as a (path, entry) tuple.
 
171
        The order that they are yielded is:
 
172
 
 
173
        Directories are walked in a depth-first lexicographical order,
 
174
        however, whenever a directory is reached, all of its direct child
 
175
        nodes are yielded in  lexicographical order before yielding the
 
176
        grandchildren.
 
177
 
 
178
        For example, in the tree::
 
179
 
 
180
           a/
 
181
             b/
 
182
               c
 
183
             d/
 
184
               e
 
185
           f/
 
186
             g
 
187
 
 
188
        The yield order (ignoring root) would be::
 
189
 
 
190
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
 
191
 
 
192
        :param yield_parents: If True, yield the parents from the root leading
 
193
            down to specific_file_ids that have been requested. This has no
 
194
            impact if specific_file_ids is None.
 
195
        """
 
196
        raise NotImplementedError(self.iter_entries_by_dir)
 
197
 
 
198
    def iter_child_entries(self, file_id, path=None):
 
199
        """Iterate over the children of a directory or tree reference.
 
200
 
 
201
        :param file_id: File id of the directory/tree-reference
 
202
        :param path: Optional path of the directory
 
203
        :raise NoSuchId: When the file_id does not exist
 
204
        :return: Iterator over entries in the directory
 
205
        """
 
206
        raise NotImplementedError(self.iter_child_entries)
 
207
 
 
208
    def list_files(self, include_root=False, from_dir=None, recursive=True):
 
209
        """List all files in this tree.
 
210
 
 
211
        :param include_root: Whether to include the entry for the tree root
 
212
        :param from_dir: Directory under which to list files
 
213
        :param recursive: Whether to list files recursively
 
214
        :return: iterator over tuples of (path, versioned, kind, file_id,
 
215
            inventory entry)
 
216
        """
 
217
        raise NotImplementedError(self.list_files)
178
218
 
179
219
    def iter_references(self):
180
 
        for path, entry in self.iter_entries_by_dir():
181
 
            if entry.kind == 'tree-reference':
182
 
                yield path, entry.file_id
 
220
        if self.supports_tree_reference():
 
221
            for path, entry in self.iter_entries_by_dir():
 
222
                if entry.kind == 'tree-reference':
 
223
                    yield path, entry.file_id
183
224
 
184
225
    def kind(self, file_id):
185
226
        raise NotImplementedError("Tree subclass %s must implement kind"
186
227
            % self.__class__.__name__)
187
228
 
 
229
    def stored_kind(self, file_id):
 
230
        """File kind stored for this file_id.
 
231
 
 
232
        May not match kind on disk for working trees.  Always available
 
233
        for versioned files, even when the file itself is missing.
 
234
        """
 
235
        return self.kind(file_id)
 
236
 
188
237
    def path_content_summary(self, path):
189
238
        """Get a summary of the information about path.
190
 
        
 
239
 
 
240
        All the attributes returned are for the canonical form, not the
 
241
        convenient form (if content filters are in use.)
 
242
 
191
243
        :param path: A relative path within the tree.
192
244
        :return: A tuple containing kind, size, exec, sha1-or-link.
193
245
            Kind is always present (see tree.kind()).
194
 
            size is present if kind is file, None otherwise.
 
246
            size is present if kind is file and the size of the 
 
247
                canonical form can be cheaply determined, None otherwise.
195
248
            exec is None unless kind is file and the platform supports the 'x'
196
249
                bit.
197
250
            sha1-or-link is the link target if kind is symlink, or the sha1 if
218
271
    def _file_size(self, entry, stat_value):
219
272
        raise NotImplementedError(self._file_size)
220
273
 
221
 
    def _get_inventory(self):
222
 
        return self._inventory
223
 
    
224
274
    def get_file(self, file_id, path=None):
225
275
        """Return a file object for the file file_id in the tree.
226
 
        
 
276
 
227
277
        If both file_id and path are defined, it is implementation defined as
228
278
        to which one is used.
229
279
        """
230
280
        raise NotImplementedError(self.get_file)
231
281
 
 
282
    def get_file_with_stat(self, file_id, path=None):
 
283
        """Get a file handle and stat object for file_id.
 
284
 
 
285
        The default implementation returns (self.get_file, None) for backwards
 
286
        compatibility.
 
287
 
 
288
        :param file_id: The file id to read.
 
289
        :param path: The path of the file, if it is known.
 
290
        :return: A tuple (file_handle, stat_value_or_None). If the tree has
 
291
            no stat facility, or need for a stat cache feedback during commit,
 
292
            it may return None for the second element of the tuple.
 
293
        """
 
294
        return (self.get_file(file_id, path), None)
 
295
 
 
296
    def get_file_text(self, file_id, path=None):
 
297
        """Return the byte content of a file.
 
298
 
 
299
        :param file_id: The file_id of the file.
 
300
        :param path: The path of the file.
 
301
 
 
302
        If both file_id and path are supplied, an implementation may use
 
303
        either one.
 
304
 
 
305
        :returns: A single byte string for the whole file.
 
306
        """
 
307
        my_file = self.get_file(file_id, path)
 
308
        try:
 
309
            return my_file.read()
 
310
        finally:
 
311
            my_file.close()
 
312
 
 
313
    def get_file_lines(self, file_id, path=None):
 
314
        """Return the content of a file, as lines.
 
315
 
 
316
        :param file_id: The file_id of the file.
 
317
        :param path: The path of the file.
 
318
 
 
319
        If both file_id and path are supplied, an implementation may use
 
320
        either one.
 
321
        """
 
322
        return osutils.split_lines(self.get_file_text(file_id, path))
 
323
 
 
324
    def get_file_verifier(self, file_id, path=None, stat_value=None):
 
325
        """Return a verifier for a file.
 
326
 
 
327
        The default implementation returns a sha1.
 
328
 
 
329
        :param file_id: The handle for this file.
 
330
        :param path: The path that this file can be found at.
 
331
            These must point to the same object.
 
332
        :param stat_value: Optional stat value for the object
 
333
        :return: Tuple with verifier name and verifier data
 
334
        """
 
335
        return ("SHA1", self.get_file_sha1(file_id, path=path,
 
336
            stat_value=stat_value))
 
337
 
 
338
    def get_file_sha1(self, file_id, path=None, stat_value=None):
 
339
        """Return the SHA1 file for a file.
 
340
 
 
341
        :note: callers should use get_file_verifier instead
 
342
            where possible, as the underlying repository implementation may
 
343
            have quicker access to a non-sha1 verifier.
 
344
 
 
345
        :param file_id: The handle for this file.
 
346
        :param path: The path that this file can be found at.
 
347
            These must point to the same object.
 
348
        :param stat_value: Optional stat value for the object
 
349
        """
 
350
        raise NotImplementedError(self.get_file_sha1)
 
351
 
232
352
    def get_file_mtime(self, file_id, path=None):
233
353
        """Return the modification time for a file.
234
354
 
238
358
        """
239
359
        raise NotImplementedError(self.get_file_mtime)
240
360
 
241
 
    def get_file_by_path(self, path):
242
 
        return self.get_file(self._inventory.path2id(path), path)
 
361
    def get_file_size(self, file_id):
 
362
        """Return the size of a file in bytes.
 
363
 
 
364
        This applies only to regular files.  If invoked on directories or
 
365
        symlinks, it will return None.
 
366
        :param file_id: The file-id of the file
 
367
        """
 
368
        raise NotImplementedError(self.get_file_size)
 
369
 
 
370
    def is_executable(self, file_id, path=None):
 
371
        """Check if a file is executable.
 
372
 
 
373
        :param file_id: The handle for this file.
 
374
        :param path: The path that this file can be found at.
 
375
            These must point to the same object.
 
376
        """
 
377
        raise NotImplementedError(self.is_executable)
243
378
 
244
379
    def iter_files_bytes(self, desired_files):
245
380
        """Iterate through file contents.
267
402
            cur_file = (self.get_file_text(file_id),)
268
403
            yield identifier, cur_file
269
404
 
270
 
    def get_symlink_target(self, file_id):
 
405
    def get_symlink_target(self, file_id, path=None):
271
406
        """Get the target for a given file_id.
272
407
 
273
408
        It is assumed that the caller already knows that file_id is referencing
274
409
        a symlink.
275
410
        :param file_id: Handle for the symlink entry.
 
411
        :param path: The path of the file.
 
412
        If both file_id and path are supplied, an implementation may use
 
413
        either one.
276
414
        :return: The path the symlink points to.
277
415
        """
278
416
        raise NotImplementedError(self.get_symlink_target)
281
419
        """Return the file_id for the root of this tree."""
282
420
        raise NotImplementedError(self.get_root_id)
283
421
 
284
 
    def annotate_iter(self, file_id):
 
422
    def annotate_iter(self, file_id,
 
423
                      default_revision=_mod_revision.CURRENT_REVISION):
285
424
        """Return an iterator of revision_id, line tuples.
286
425
 
287
426
        For working trees (and mutable trees in general), the special
288
427
        revision_id 'current:' will be used for lines that are new in this
289
428
        tree, e.g. uncommitted changes.
290
429
        :param file_id: The file to produce an annotated version from
 
430
        :param default_revision: For lines that don't match a basis, mark them
 
431
            with this revision id. Not all implementations will make use of
 
432
            this value.
291
433
        """
292
434
        raise NotImplementedError(self.annotate_iter)
293
435
 
294
 
    def plan_file_merge(self, file_id, other):
295
 
        """Generate a merge plan based on annotations.
296
 
 
297
 
        If the file contains uncommitted changes in this tree, they will be
298
 
        attributed to the 'current:' pseudo-revision.  If the file contains
299
 
        uncommitted changes in the other tree, they will be assigned to the
300
 
        'other:' pseudo-revision.
301
 
        """
302
 
        from bzrlib import merge, versionedfile
 
436
    def _get_plan_merge_data(self, file_id, other, base):
 
437
        from bzrlib import versionedfile
303
438
        vf = versionedfile._PlanMergeVersionedFile(file_id)
304
439
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
305
440
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
306
 
        return vf.plan_merge(last_revision_a, last_revision_b)
 
441
        if base is None:
 
442
            last_revision_base = None
 
443
        else:
 
444
            last_revision_base = base._get_file_revision(file_id, vf, 'base:')
 
445
        return vf, last_revision_a, last_revision_b, last_revision_base
 
446
 
 
447
    def plan_file_merge(self, file_id, other, base=None):
 
448
        """Generate a merge plan based on annotations.
 
449
 
 
450
        If the file contains uncommitted changes in this tree, they will be
 
451
        attributed to the 'current:' pseudo-revision.  If the file contains
 
452
        uncommitted changes in the other tree, they will be assigned to the
 
453
        'other:' pseudo-revision.
 
454
        """
 
455
        data = self._get_plan_merge_data(file_id, other, base)
 
456
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
457
        return vf.plan_merge(last_revision_a, last_revision_b,
 
458
                             last_revision_base)
 
459
 
 
460
    def plan_file_lca_merge(self, file_id, other, base=None):
 
461
        """Generate a merge plan based lca-newness.
 
462
 
 
463
        If the file contains uncommitted changes in this tree, they will be
 
464
        attributed to the 'current:' pseudo-revision.  If the file contains
 
465
        uncommitted changes in the other tree, they will be assigned to the
 
466
        'other:' pseudo-revision.
 
467
        """
 
468
        data = self._get_plan_merge_data(file_id, other, base)
 
469
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
470
        return vf.plan_lca_merge(last_revision_a, last_revision_b,
 
471
                                 last_revision_base)
 
472
 
 
473
    def _iter_parent_trees(self):
 
474
        """Iterate through parent trees, defaulting to Tree.revision_tree."""
 
475
        for revision_id in self.get_parent_ids():
 
476
            try:
 
477
                yield self.revision_tree(revision_id)
 
478
            except errors.NoSuchRevisionInTree:
 
479
                yield self.repository.revision_tree(revision_id)
307
480
 
308
481
    def _get_file_revision(self, file_id, vf, tree_revision):
309
 
        def file_revision(revision_tree):
310
 
            revision_tree.lock_read()
311
 
            try:
312
 
                return revision_tree.inventory[file_id].revision
313
 
            finally:
314
 
                revision_tree.unlock()
315
 
 
316
 
        def iter_parent_trees():
317
 
            for revision_id in self.get_parent_ids():
318
 
                try:
319
 
                    yield self.revision_tree(revision_id)
320
 
                except:
321
 
                    yield self.repository.revision_tree(revision_id)
322
 
 
323
 
        if getattr(self, '_get_weave', None) is None:
 
482
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
 
483
 
 
484
        if getattr(self, '_repository', None) is None:
324
485
            last_revision = tree_revision
325
 
            parent_revisions = [file_revision(t) for t in iter_parent_trees()]
326
 
            vf.add_lines(last_revision, parent_revisions,
327
 
                         self.get_file(file_id).readlines())
 
486
            parent_keys = [(file_id, t.get_file_revision(file_id)) for t in
 
487
                self._iter_parent_trees()]
 
488
            vf.add_lines((file_id, last_revision), parent_keys,
 
489
                         self.get_file_lines(file_id))
328
490
            repo = self.branch.repository
329
 
            transaction = repo.get_transaction()
330
 
            base_vf = repo.weave_store.get_weave(file_id, transaction)
 
491
            base_vf = repo.texts
331
492
        else:
332
 
            last_revision = file_revision(self)
333
 
            base_vf = self._get_weave(file_id)
334
 
        vf.fallback_versionedfiles.append(base_vf)
 
493
            last_revision = self.get_file_revision(file_id)
 
494
            base_vf = self._repository.texts
 
495
        if base_vf not in vf.fallback_versionedfiles:
 
496
            vf.fallback_versionedfiles.append(base_vf)
335
497
        return last_revision
336
498
 
337
 
    inventory = property(_get_inventory,
338
 
                         doc="Inventory of this Tree")
339
 
 
340
499
    def _check_retrieved(self, ie, f):
341
500
        if not __debug__:
342
 
            return  
343
 
        fp = fingerprint_file(f)
 
501
            return
 
502
        fp = osutils.fingerprint_file(f)
344
503
        f.seek(0)
345
 
        
 
504
 
346
505
        if ie.text_size is not None:
347
506
            if ie.text_size != fp['size']:
348
 
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
 
507
                raise errors.BzrError(
 
508
                        "mismatched size for file %r in %r" %
 
509
                        (ie.file_id, self._store),
349
510
                        ["inventory expects %d bytes" % ie.text_size,
350
511
                         "file is actually %d bytes" % fp['size'],
351
512
                         "store is probably damaged/corrupt"])
352
513
 
353
514
        if ie.text_sha1 != fp['sha1']:
354
 
            raise BzrError("wrong SHA-1 for file %r in %r" % (ie.file_id, self._store),
 
515
            raise errors.BzrError("wrong SHA-1 for file %r in %r" %
 
516
                    (ie.file_id, self._store),
355
517
                    ["inventory expects %s" % ie.text_sha1,
356
518
                     "file is actually %s" % fp['sha1'],
357
519
                     "store is probably damaged/corrupt"])
358
520
 
359
 
    @needs_read_lock
360
521
    def path2id(self, path):
361
522
        """Return the id for path in this tree."""
362
 
        return self._inventory.path2id(path)
 
523
        raise NotImplementedError(self.path2id)
363
524
 
364
525
    def paths2ids(self, paths, trees=[], require_versioned=True):
365
526
        """Return all the ids that can be reached by walking from paths.
366
 
        
 
527
 
367
528
        Each path is looked up in this tree and any extras provided in
368
529
        trees, and this is repeated recursively: the children in an extra tree
369
530
        of a directory that has been renamed under a provided path in this tree
380
541
        """
381
542
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
382
543
 
383
 
    def print_file(self, file_id):
384
 
        """Print file with id `file_id` to stdout."""
385
 
        import sys
386
 
        sys.stdout.write(self.get_file_text(file_id))
 
544
    def iter_children(self, file_id):
 
545
        """Iterate over the file ids of the children of an entry.
 
546
 
 
547
        :param file_id: File id of the entry
 
548
        :return: Iterator over child file ids.
 
549
        """
 
550
        raise NotImplementedError(self.iter_children)
387
551
 
388
552
    def lock_read(self):
 
553
        """Lock this tree for multiple read only operations.
 
554
 
 
555
        :return: A bzrlib.lock.LogicalLockResult.
 
556
        """
389
557
        pass
390
558
 
391
559
    def revision_tree(self, revision_id):
393
561
 
394
562
        The intention of this method is to allow access to possibly cached
395
563
        tree data. Implementors of this method should raise NoSuchRevision if
396
 
        the tree is not locally available, even if they could obtain the 
397
 
        tree via a repository or some other means. Callers are responsible 
 
564
        the tree is not locally available, even if they could obtain the
 
565
        tree via a repository or some other means. Callers are responsible
398
566
        for finding the ultimate source for a revision tree.
399
567
 
400
568
        :param revision_id: The revision_id of the requested tree.
405
573
 
406
574
    def unknowns(self):
407
575
        """What files are present in this tree and unknown.
408
 
        
 
576
 
409
577
        :return: an iterator over the unknown files.
410
578
        """
411
579
        return iter([])
418
586
 
419
587
        :return: set of paths.
420
588
        """
421
 
        # NB: we specifically *don't* call self.has_filename, because for
422
 
        # WorkingTrees that can indicate files that exist on disk but that 
423
 
        # are not versioned.
424
 
        pred = self.inventory.has_filename
425
 
        return set((p for p in paths if not pred(p)))
 
589
        raise NotImplementedError(self.filter_unversioned_files)
426
590
 
427
591
    def walkdirs(self, prefix=""):
428
592
        """Walk the contents of this tree from path down.
430
594
        This yields all the data about the contents of a directory at a time.
431
595
        After each directory has been yielded, if the caller has mutated the
432
596
        list to exclude some directories, they are then not descended into.
433
 
        
 
597
 
434
598
        The data yielded is of the form:
435
599
        ((directory-relpath, directory-path-from-root, directory-fileid),
436
 
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id, 
 
600
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id,
437
601
          versioned_kind), ...]),
438
602
         - directory-relpath is the containing dirs relpath from prefix
439
603
         - directory-path-from-root is the containing dirs path from /
446
610
         - lstat is the stat data *if* the file was statted.
447
611
         - path_from_tree_root is the path from the root of the tree.
448
612
         - file_id is the file_id if the entry is versioned.
449
 
         - versioned_kind is the kind of the file as last recorded in the 
 
613
         - versioned_kind is the kind of the file as last recorded in the
450
614
           versioning system. If 'unknown' the file is not versioned.
451
615
        One of 'kind' and 'versioned_kind' must not be 'unknown'.
452
616
 
457
621
        """
458
622
        raise NotImplementedError(self.walkdirs)
459
623
 
460
 
 
461
 
class EmptyTree(Tree):
462
 
 
463
 
    def __init__(self):
464
 
        self._inventory = Inventory(root_id=None)
465
 
        symbol_versioning.warn('EmptyTree is deprecated as of bzr 0.9 please'
466
 
                               ' use repository.revision_tree instead.',
467
 
                               DeprecationWarning, stacklevel=2)
468
 
 
469
 
    def get_parent_ids(self):
470
 
        return []
471
 
 
472
 
    def get_symlink_target(self, file_id):
473
 
        return None
474
 
 
475
 
    def has_filename(self, filename):
 
624
    def supports_content_filtering(self):
476
625
        return False
477
626
 
478
 
    def kind(self, file_id):
479
 
        assert self._inventory[file_id].kind == "directory"
480
 
        return "directory"
481
 
 
482
 
    def list_files(self, include_root=False):
483
 
        return iter([])
484
 
    
485
 
    def __contains__(self, file_id):
486
 
        return (file_id in self._inventory)
487
 
 
488
 
    def get_file_sha1(self, file_id, path=None, stat_value=None):
489
 
        return None
490
 
 
491
 
 
492
 
######################################################################
493
 
# diff
494
 
 
495
 
# TODO: Merge these two functions into a single one that can operate
496
 
# on either a whole tree or a set of files.
497
 
 
498
 
# TODO: Return the diff in order by filename, not by category or in
499
 
# random order.  Can probably be done by lock-stepping through the
500
 
# filenames from both trees.
501
 
 
502
 
 
503
 
def file_status(filename, old_tree, new_tree):
504
 
    """Return single-letter status, old and new names for a file.
505
 
 
506
 
    The complexity here is in deciding how to represent renames;
507
 
    many complex cases are possible.
 
627
    def _content_filter_stack(self, path=None, file_id=None):
 
628
        """The stack of content filters for a path if filtering is supported.
 
629
 
 
630
        Readers will be applied in first-to-last order.
 
631
        Writers will be applied in last-to-first order.
 
632
        Either the path or the file-id needs to be provided.
 
633
 
 
634
        :param path: path relative to the root of the tree
 
635
            or None if unknown
 
636
        :param file_id: file_id or None if unknown
 
637
        :return: the list of filters - [] if there are none
 
638
        """
 
639
        filter_pref_names = filters._get_registered_names()
 
640
        if len(filter_pref_names) == 0:
 
641
            return []
 
642
        if path is None:
 
643
            path = self.id2path(file_id)
 
644
        prefs = self.iter_search_rules([path], filter_pref_names).next()
 
645
        stk = filters._get_filter_stack_for(prefs)
 
646
        if 'filters' in debug.debug_flags:
 
647
            trace.note(gettext("*** {0} content-filter: {1} => {2!r}").format(path,prefs,stk))
 
648
        return stk
 
649
 
 
650
    def _content_filter_stack_provider(self):
 
651
        """A function that returns a stack of ContentFilters.
 
652
 
 
653
        The function takes a path (relative to the top of the tree) and a
 
654
        file-id as parameters.
 
655
 
 
656
        :return: None if content filtering is not supported by this tree.
 
657
        """
 
658
        if self.supports_content_filtering():
 
659
            return lambda path, file_id: \
 
660
                    self._content_filter_stack(path, file_id)
 
661
        else:
 
662
            return None
 
663
 
 
664
    def iter_search_rules(self, path_names, pref_names=None,
 
665
        _default_searcher=None):
 
666
        """Find the preferences for filenames in a tree.
 
667
 
 
668
        :param path_names: an iterable of paths to find attributes for.
 
669
          Paths are given relative to the root of the tree.
 
670
        :param pref_names: the list of preferences to lookup - None for all
 
671
        :param _default_searcher: private parameter to assist testing - don't use
 
672
        :return: an iterator of tuple sequences, one per path-name.
 
673
          See _RulesSearcher.get_items for details on the tuple sequence.
 
674
        """
 
675
        if _default_searcher is None:
 
676
            _default_searcher = rules._per_user_searcher
 
677
        searcher = self._get_rules_searcher(_default_searcher)
 
678
        if searcher is not None:
 
679
            if pref_names is not None:
 
680
                for path in path_names:
 
681
                    yield searcher.get_selected_items(path, pref_names)
 
682
            else:
 
683
                for path in path_names:
 
684
                    yield searcher.get_items(path)
 
685
 
 
686
    def _get_rules_searcher(self, default_searcher):
 
687
        """Get the RulesSearcher for this tree given the default one."""
 
688
        searcher = default_searcher
 
689
        return searcher
 
690
 
 
691
 
 
692
class InventoryTree(Tree):
 
693
    """A tree that relies on an inventory for its metadata.
 
694
 
 
695
    Trees contain an `Inventory` object, and also know how to retrieve
 
696
    file texts mentioned in the inventory, either from a working
 
697
    directory or from a store.
 
698
 
 
699
    It is possible for trees to contain files that are not described
 
700
    in their inventory or vice versa; for this use `filenames()`.
 
701
 
 
702
    Subclasses should set the _inventory attribute, which is considered
 
703
    private to external API users.
508
704
    """
509
 
    old_inv = old_tree.inventory
510
 
    new_inv = new_tree.inventory
511
 
    new_id = new_inv.path2id(filename)
512
 
    old_id = old_inv.path2id(filename)
513
 
 
514
 
    if not new_id and not old_id:
515
 
        # easy: doesn't exist in either; not versioned at all
516
 
        if new_tree.is_ignored(filename):
517
 
            return 'I', None, None
518
 
        else:
519
 
            return '?', None, None
520
 
    elif new_id:
521
 
        # There is now a file of this name, great.
522
 
        pass
523
 
    else:
524
 
        # There is no longer a file of this name, but we can describe
525
 
        # what happened to the file that used to have
526
 
        # this name.  There are two possibilities: either it was
527
 
        # deleted entirely, or renamed.
528
 
        assert old_id
529
 
        if new_inv.has_id(old_id):
530
 
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
531
 
        else:
532
 
            return 'D', old_inv.id2path(old_id), None
533
 
 
534
 
    # if the file_id is new in this revision, it is added
535
 
    if new_id and not old_inv.has_id(new_id):
536
 
        return 'A'
537
 
 
538
 
    # if there used to be a file of this name, but that ID has now
539
 
    # disappeared, it is deleted
540
 
    if old_id and not new_inv.has_id(old_id):
541
 
        return 'D'
542
 
 
543
 
    return 'wtf?'
544
 
 
545
 
    
546
 
 
547
 
def find_renames(old_inv, new_inv):
548
 
    for file_id in old_inv:
549
 
        if file_id not in new_inv:
550
 
            continue
551
 
        old_name = old_inv.id2path(file_id)
552
 
        new_name = new_inv.id2path(file_id)
553
 
        if old_name != new_name:
554
 
            yield (old_name, new_name)
555
 
            
 
705
 
 
706
    def get_canonical_inventory_paths(self, paths):
 
707
        """Like get_canonical_inventory_path() but works on multiple items.
 
708
 
 
709
        :param paths: A sequence of paths relative to the root of the tree.
 
710
        :return: A list of paths, with each item the corresponding input path
 
711
        adjusted to account for existing elements that match case
 
712
        insensitively.
 
713
        """
 
714
        return list(self._yield_canonical_inventory_paths(paths))
 
715
 
 
716
    def get_canonical_inventory_path(self, path):
 
717
        """Returns the first inventory item that case-insensitively matches path.
 
718
 
 
719
        If a path matches exactly, it is returned. If no path matches exactly
 
720
        but more than one path matches case-insensitively, it is implementation
 
721
        defined which is returned.
 
722
 
 
723
        If no path matches case-insensitively, the input path is returned, but
 
724
        with as many path entries that do exist changed to their canonical
 
725
        form.
 
726
 
 
727
        If you need to resolve many names from the same tree, you should
 
728
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
729
 
 
730
        :param path: A paths relative to the root of the tree.
 
731
        :return: The input path adjusted to account for existing elements
 
732
        that match case insensitively.
 
733
        """
 
734
        return self._yield_canonical_inventory_paths([path]).next()
 
735
 
 
736
    def _yield_canonical_inventory_paths(self, paths):
 
737
        for path in paths:
 
738
            # First, if the path as specified exists exactly, just use it.
 
739
            if self.path2id(path) is not None:
 
740
                yield path
 
741
                continue
 
742
            # go walkin...
 
743
            cur_id = self.get_root_id()
 
744
            cur_path = ''
 
745
            bit_iter = iter(path.split("/"))
 
746
            for elt in bit_iter:
 
747
                lelt = elt.lower()
 
748
                new_path = None
 
749
                for child in self.iter_children(cur_id):
 
750
                    try:
 
751
                        # XXX: it seem like if the child is known to be in the
 
752
                        # tree, we shouldn't need to go from its id back to
 
753
                        # its path -- mbp 2010-02-11
 
754
                        #
 
755
                        # XXX: it seems like we could be more efficient
 
756
                        # by just directly looking up the original name and
 
757
                        # only then searching all children; also by not
 
758
                        # chopping paths so much. -- mbp 2010-02-11
 
759
                        child_base = os.path.basename(self.id2path(child))
 
760
                        if (child_base == elt):
 
761
                            # if we found an exact match, we can stop now; if
 
762
                            # we found an approximate match we need to keep
 
763
                            # searching because there might be an exact match
 
764
                            # later.  
 
765
                            cur_id = child
 
766
                            new_path = osutils.pathjoin(cur_path, child_base)
 
767
                            break
 
768
                        elif child_base.lower() == lelt:
 
769
                            cur_id = child
 
770
                            new_path = osutils.pathjoin(cur_path, child_base)
 
771
                    except errors.NoSuchId:
 
772
                        # before a change is committed we can see this error...
 
773
                        continue
 
774
                if new_path:
 
775
                    cur_path = new_path
 
776
                else:
 
777
                    # got to the end of this directory and no entries matched.
 
778
                    # Return what matched so far, plus the rest as specified.
 
779
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
780
                    break
 
781
            yield cur_path
 
782
        # all done.
 
783
 
 
784
    @deprecated_method(deprecated_in((2, 5, 0)))
 
785
    def _get_inventory(self):
 
786
        return self._inventory
 
787
 
 
788
    inventory = property(_get_inventory,
 
789
                         doc="Inventory of this Tree")
 
790
 
 
791
    def _get_root_inventory(self):
 
792
        return self._inventory
 
793
 
 
794
    root_inventory = property(_get_root_inventory,
 
795
        doc="Root inventory of this tree")
 
796
 
 
797
    def _unpack_file_id(self, file_id):
 
798
        """Find the inventory and inventory file id for a tree file id.
 
799
 
 
800
        :param file_id: The tree file id, as bytestring or tuple
 
801
        :return: Inventory and inventory file id
 
802
        """
 
803
        if isinstance(file_id, tuple):
 
804
            if len(file_id) != 1:
 
805
                raise ValueError("nested trees not yet supported: %r" % file_id)
 
806
            file_id = file_id[0]
 
807
        return self.root_inventory, file_id
 
808
 
 
809
    @needs_read_lock
 
810
    def path2id(self, path):
 
811
        """Return the id for path in this tree."""
 
812
        return self._path2inv_file_id(path)[1]
 
813
 
 
814
    def _path2inv_file_id(self, path):
 
815
        """Lookup a inventory and inventory file id by path.
 
816
 
 
817
        :param path: Path to look up
 
818
        :return: tuple with inventory and inventory file id
 
819
        """
 
820
        # FIXME: Support nested trees
 
821
        return self.root_inventory, self.root_inventory.path2id(path)
 
822
 
 
823
    def id2path(self, file_id):
 
824
        """Return the path for a file id.
 
825
 
 
826
        :raises NoSuchId:
 
827
        """
 
828
        inventory, file_id = self._unpack_file_id(file_id)
 
829
        return inventory.id2path(file_id)
 
830
 
 
831
    def has_id(self, file_id):
 
832
        inventory, file_id = self._unpack_file_id(file_id)
 
833
        return inventory.has_id(file_id)
 
834
 
 
835
    def has_or_had_id(self, file_id):
 
836
        inventory, file_id = self._unpack_file_id(file_id)
 
837
        return inventory.has_id(file_id)
 
838
 
 
839
    def all_file_ids(self):
 
840
        return set(
 
841
            [entry.file_id for path, entry in self.iter_entries_by_dir()])
 
842
 
 
843
    @deprecated_method(deprecated_in((2, 4, 0)))
 
844
    def __iter__(self):
 
845
        return iter(self.all_file_ids())
 
846
 
 
847
    def filter_unversioned_files(self, paths):
 
848
        """Filter out paths that are versioned.
 
849
 
 
850
        :return: set of paths.
 
851
        """
 
852
        # NB: we specifically *don't* call self.has_filename, because for
 
853
        # WorkingTrees that can indicate files that exist on disk but that
 
854
        # are not versioned.
 
855
        return set((p for p in paths if self.path2id(p) is None))
 
856
 
 
857
    @needs_read_lock
 
858
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
 
859
        """Walk the tree in 'by_dir' order.
 
860
 
 
861
        This will yield each entry in the tree as a (path, entry) tuple.
 
862
        The order that they are yielded is:
 
863
 
 
864
        See Tree.iter_entries_by_dir for details.
 
865
 
 
866
        :param yield_parents: If True, yield the parents from the root leading
 
867
            down to specific_file_ids that have been requested. This has no
 
868
            impact if specific_file_ids is None.
 
869
        """
 
870
        if specific_file_ids is None:
 
871
            inventory_file_ids = None
 
872
        else:
 
873
            inventory_file_ids = []
 
874
            for tree_file_id in specific_file_ids:
 
875
                inventory, inv_file_id = self._unpack_file_id(tree_file_id)
 
876
                if not inventory is self.root_inventory: # for now
 
877
                    raise AssertionError("%r != %r" % (
 
878
                        inventory, self.root_inventory))
 
879
                inventory_file_ids.append(inv_file_id)
 
880
        # FIXME: Handle nested trees
 
881
        return self.root_inventory.iter_entries_by_dir(
 
882
            specific_file_ids=inventory_file_ids, yield_parents=yield_parents)
 
883
 
 
884
    @needs_read_lock
 
885
    def iter_child_entries(self, file_id, path=None):
 
886
        inv, inv_file_id = self._unpack_file_id(file_id)
 
887
        return inv[inv_file_id].children.itervalues()
 
888
 
 
889
    @deprecated_method(deprecated_in((2, 5, 0)))
 
890
    def get_file_by_path(self, path):
 
891
        return self.get_file(self.path2id(path), path)
 
892
 
 
893
    def iter_children(self, file_id, path=None):
 
894
        """See Tree.iter_children."""
 
895
        entry = self.iter_entries_by_dir([file_id]).next()[1]
 
896
        for child in getattr(entry, 'children', {}).itervalues():
 
897
            yield child.file_id
 
898
 
556
899
 
557
900
def find_ids_across_trees(filenames, trees, require_versioned=True):
558
901
    """Find the ids corresponding to specified filenames.
559
 
    
 
902
 
560
903
    All matches in all trees will be used, and all children of matched
561
904
    directories will be used.
562
905
 
564
907
        None)
565
908
    :param trees: The trees to find file_ids within
566
909
    :param require_versioned: if true, all specified filenames must occur in
567
 
    at least one tree.
 
910
        at least one tree.
568
911
    :return: a set of file ids for the specified filenames and their children.
569
912
    """
570
913
    if not filenames:
576
919
 
577
920
def _find_ids_across_trees(filenames, trees, require_versioned):
578
921
    """Find the ids corresponding to specified filenames.
579
 
    
 
922
 
580
923
    All matches in all trees will be used, but subdirectories are not scanned.
581
924
 
582
925
    :param filenames: The filenames to find file_ids for
603
946
 
604
947
def _find_children_across_trees(specified_ids, trees):
605
948
    """Return a set including specified ids and their children.
606
 
    
 
949
 
607
950
    All matches in all trees will be used.
608
951
 
609
952
    :param trees: The trees to find file_ids within
610
 
    :return: a set containing all specified ids and their children 
 
953
    :return: a set containing all specified ids and their children
611
954
    """
612
955
    interesting_ids = set(specified_ids)
613
956
    pending = interesting_ids
617
960
        new_pending = set()
618
961
        for file_id in pending:
619
962
            for tree in trees:
620
 
                if not tree.has_id(file_id):
 
963
                if not tree.has_or_had_id(file_id):
621
964
                    continue
622
 
                entry = tree.inventory[file_id]
623
 
                for child in getattr(entry, 'children', {}).itervalues():
624
 
                    if child.file_id not in interesting_ids:
625
 
                        new_pending.add(child.file_id)
 
965
                for child_id in tree.iter_children(file_id):
 
966
                    if child_id not in interesting_ids:
 
967
                        new_pending.add(child_id)
626
968
        interesting_ids.update(new_pending)
627
969
        pending = new_pending
628
970
    return interesting_ids
639
981
    will pass through to InterTree as appropriate.
640
982
    """
641
983
 
 
984
    # Formats that will be used to test this InterTree. If both are
 
985
    # None, this InterTree will not be tested (e.g. because a complex
 
986
    # setup is required)
 
987
    _matching_from_tree_format = None
 
988
    _matching_to_tree_format = None
 
989
 
642
990
    _optimisers = []
643
991
 
 
992
    @classmethod
 
993
    def is_compatible(kls, source, target):
 
994
        # The default implementation is naive and uses the public API, so
 
995
        # it works for all trees.
 
996
        return True
 
997
 
 
998
    def _changes_from_entries(self, source_entry, target_entry,
 
999
        source_path=None, target_path=None):
 
1000
        """Generate a iter_changes tuple between source_entry and target_entry.
 
1001
 
 
1002
        :param source_entry: An inventory entry from self.source, or None.
 
1003
        :param target_entry: An inventory entry from self.target, or None.
 
1004
        :param source_path: The path of source_entry, if known. If not known
 
1005
            it will be looked up.
 
1006
        :param target_path: The path of target_entry, if known. If not known
 
1007
            it will be looked up.
 
1008
        :return: A tuple, item 0 of which is an iter_changes result tuple, and
 
1009
            item 1 is True if there are any changes in the result tuple.
 
1010
        """
 
1011
        if source_entry is None:
 
1012
            if target_entry is None:
 
1013
                return None
 
1014
            file_id = target_entry.file_id
 
1015
        else:
 
1016
            file_id = source_entry.file_id
 
1017
        if source_entry is not None:
 
1018
            source_versioned = True
 
1019
            source_name = source_entry.name
 
1020
            source_parent = source_entry.parent_id
 
1021
            if source_path is None:
 
1022
                source_path = self.source.id2path(file_id)
 
1023
            source_kind, source_executable, source_stat = \
 
1024
                self.source._comparison_data(source_entry, source_path)
 
1025
        else:
 
1026
            source_versioned = False
 
1027
            source_name = None
 
1028
            source_parent = None
 
1029
            source_kind = None
 
1030
            source_executable = None
 
1031
        if target_entry is not None:
 
1032
            target_versioned = True
 
1033
            target_name = target_entry.name
 
1034
            target_parent = target_entry.parent_id
 
1035
            if target_path is None:
 
1036
                target_path = self.target.id2path(file_id)
 
1037
            target_kind, target_executable, target_stat = \
 
1038
                self.target._comparison_data(target_entry, target_path)
 
1039
        else:
 
1040
            target_versioned = False
 
1041
            target_name = None
 
1042
            target_parent = None
 
1043
            target_kind = None
 
1044
            target_executable = None
 
1045
        versioned = (source_versioned, target_versioned)
 
1046
        kind = (source_kind, target_kind)
 
1047
        changed_content = False
 
1048
        if source_kind != target_kind:
 
1049
            changed_content = True
 
1050
        elif source_kind == 'file':
 
1051
            if not self.file_content_matches(file_id, file_id, source_path,
 
1052
                    target_path, source_stat, target_stat):
 
1053
                changed_content = True
 
1054
        elif source_kind == 'symlink':
 
1055
            if (self.source.get_symlink_target(file_id) !=
 
1056
                self.target.get_symlink_target(file_id)):
 
1057
                changed_content = True
 
1058
        elif source_kind == 'tree-reference':
 
1059
            if (self.source.get_reference_revision(file_id, source_path)
 
1060
                != self.target.get_reference_revision(file_id, target_path)):
 
1061
                    changed_content = True
 
1062
        parent = (source_parent, target_parent)
 
1063
        name = (source_name, target_name)
 
1064
        executable = (source_executable, target_executable)
 
1065
        if (changed_content is not False or versioned[0] != versioned[1]
 
1066
            or parent[0] != parent[1] or name[0] != name[1] or
 
1067
            executable[0] != executable[1]):
 
1068
            changes = True
 
1069
        else:
 
1070
            changes = False
 
1071
        return (file_id, (source_path, target_path), changed_content,
 
1072
                versioned, parent, name, kind, executable), changes
 
1073
 
644
1074
    @needs_read_lock
645
1075
    def compare(self, want_unchanged=False, specific_files=None,
646
1076
        extra_trees=None, require_versioned=False, include_root=False,
661
1091
            a PathsNotVersionedError will be thrown.
662
1092
        :param want_unversioned: Scan for unversioned paths.
663
1093
        """
664
 
        # NB: show_status depends on being able to pass in non-versioned files
665
 
        # and report them as unknown
666
1094
        trees = (self.source,)
667
1095
        if extra_trees is not None:
668
1096
            trees = trees + tuple(extra_trees)
673
1101
            # All files are unversioned, so just return an empty delta
674
1102
            # _compare_trees would think we want a complete delta
675
1103
            result = delta.TreeDelta()
676
 
            fake_entry = InventoryFile('unused', 'unused', 'unused')
 
1104
            fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
677
1105
            result.unversioned = [(path, None,
678
1106
                self.target._comparison_data(fake_entry, path)[0]) for path in
679
1107
                specific_files]
683
1111
            require_versioned=require_versioned,
684
1112
            want_unversioned=want_unversioned)
685
1113
 
686
 
    def _iter_changes(self, include_unchanged=False,
 
1114
    def iter_changes(self, include_unchanged=False,
687
1115
                      specific_files=None, pb=None, extra_trees=[],
688
1116
                      require_versioned=True, want_unversioned=False):
689
1117
        """Generate an iterator of changes between trees.
709
1137
        :param require_versioned: Raise errors.PathsNotVersionedError if a
710
1138
            path in the specific_files list is not versioned in one of
711
1139
            source, target or extra_trees.
 
1140
        :param specific_files: An optional list of file paths to restrict the
 
1141
            comparison to. When mapping filenames to ids, all matches in all
 
1142
            trees (including optional extra_trees) are used, and all children
 
1143
            of matched directories are included. The parents in the target tree
 
1144
            of the specific files up to and including the root of the tree are
 
1145
            always evaluated for changes too.
712
1146
        :param want_unversioned: Should unversioned files be returned in the
713
1147
            output. An unversioned file is defined as one with (False, False)
714
1148
            for the versioned pair.
715
1149
        """
716
 
        result = []
717
1150
        lookup_trees = [self.source]
718
1151
        if extra_trees:
719
1152
             lookup_trees.extend(extra_trees)
 
1153
        # The ids of items we need to examine to insure delta consistency.
 
1154
        precise_file_ids = set()
 
1155
        changed_file_ids = []
720
1156
        if specific_files == []:
721
1157
            specific_file_ids = []
722
1158
        else:
723
1159
            specific_file_ids = self.target.paths2ids(specific_files,
724
1160
                lookup_trees, require_versioned=require_versioned)
 
1161
        if specific_files is not None:
 
1162
            # reparented or added entries must have their parents included
 
1163
            # so that valid deltas can be created. The seen_parents set
 
1164
            # tracks the parents that we need to have.
 
1165
            # The seen_dirs set tracks directory entries we've yielded.
 
1166
            # After outputting version object in to_entries we set difference
 
1167
            # the two seen sets and start checking parents.
 
1168
            seen_parents = set()
 
1169
            seen_dirs = set()
725
1170
        if want_unversioned:
726
1171
            all_unversioned = sorted([(p.split('/'), p) for p in
727
1172
                                     self.target.extras()
728
1173
                if specific_files is None or
729
1174
                    osutils.is_inside_any(specific_files, p)])
730
 
            all_unversioned = deque(all_unversioned)
 
1175
            all_unversioned = collections.deque(all_unversioned)
731
1176
        else:
732
 
            all_unversioned = deque()
 
1177
            all_unversioned = collections.deque()
733
1178
        to_paths = {}
734
 
        from_entries_by_dir = list(self.source.inventory.iter_entries_by_dir(
 
1179
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
735
1180
            specific_file_ids=specific_file_ids))
736
1181
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
737
 
        to_entries_by_dir = list(self.target.inventory.iter_entries_by_dir(
 
1182
        to_entries_by_dir = list(self.target.iter_entries_by_dir(
738
1183
            specific_file_ids=specific_file_ids))
739
1184
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
740
1185
        entry_count = 0
741
 
        # the unversioned path lookup only occurs on real trees - where there 
 
1186
        # the unversioned path lookup only occurs on real trees - where there
742
1187
        # can be extras. So the fake_entry is solely used to look up
743
1188
        # executable it values when execute is not supported.
744
 
        fake_entry = InventoryFile('unused', 'unused', 'unused')
745
 
        for to_path, to_entry in to_entries_by_dir:
746
 
            while all_unversioned and all_unversioned[0][0] < to_path.split('/'):
 
1189
        fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
 
1190
        for target_path, target_entry in to_entries_by_dir:
 
1191
            while (all_unversioned and
 
1192
                all_unversioned[0][0] < target_path.split('/')):
747
1193
                unversioned_path = all_unversioned.popleft()
748
 
                to_kind, to_executable, to_stat = \
 
1194
                target_kind, target_executable, target_stat = \
749
1195
                    self.target._comparison_data(fake_entry, unversioned_path[1])
750
1196
                yield (None, (None, unversioned_path[1]), True, (False, False),
751
1197
                    (None, None),
752
1198
                    (None, unversioned_path[0][-1]),
753
 
                    (None, to_kind),
754
 
                    (None, to_executable))
755
 
            file_id = to_entry.file_id
756
 
            to_paths[file_id] = to_path
 
1199
                    (None, target_kind),
 
1200
                    (None, target_executable))
 
1201
            source_path, source_entry = from_data.get(target_entry.file_id,
 
1202
                (None, None))
 
1203
            result, changes = self._changes_from_entries(source_entry,
 
1204
                target_entry, source_path=source_path, target_path=target_path)
 
1205
            to_paths[result[0]] = result[1][1]
757
1206
            entry_count += 1
758
 
            changed_content = False
759
 
            from_path, from_entry = from_data.get(file_id, (None, None))
760
 
            from_versioned = (from_entry is not None)
761
 
            if from_entry is not None:
762
 
                from_versioned = True
763
 
                from_name = from_entry.name
764
 
                from_parent = from_entry.parent_id
765
 
                from_kind, from_executable, from_stat = \
766
 
                    self.source._comparison_data(from_entry, from_path)
 
1207
            if result[3][0]:
767
1208
                entry_count += 1
768
 
            else:
769
 
                from_versioned = False
770
 
                from_kind = None
771
 
                from_parent = None
772
 
                from_name = None
773
 
                from_executable = None
774
 
            versioned = (from_versioned, True)
775
 
            to_kind, to_executable, to_stat = \
776
 
                self.target._comparison_data(to_entry, to_path)
777
 
            kind = (from_kind, to_kind)
778
 
            if kind[0] != kind[1]:
779
 
                changed_content = True
780
 
            elif from_kind == 'file':
781
 
                from_size = self.source._file_size(from_entry, from_stat)
782
 
                to_size = self.target._file_size(to_entry, to_stat)
783
 
                if from_size != to_size:
784
 
                    changed_content = True
785
 
                elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
786
 
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
787
 
                    changed_content = True
788
 
            elif from_kind == 'symlink':
789
 
                if (self.source.get_symlink_target(file_id) !=
790
 
                    self.target.get_symlink_target(file_id)):
791
 
                    changed_content = True
792
 
                elif from_kind == 'tree-reference':
793
 
                    if (self.source.get_reference_revision(file_id, from_path)
794
 
                        != self.target.get_reference_revision(file_id, to_path)):
795
 
                        changed_content = True 
796
 
            parent = (from_parent, to_entry.parent_id)
797
 
            name = (from_name, to_entry.name)
798
 
            executable = (from_executable, to_executable)
799
1209
            if pb is not None:
800
1210
                pb.update('comparing files', entry_count, num_entries)
801
 
            if (changed_content is not False or versioned[0] != versioned[1]
802
 
                or parent[0] != parent[1] or name[0] != name[1] or 
803
 
                executable[0] != executable[1] or include_unchanged):
804
 
                yield (file_id, (from_path, to_path), changed_content,
805
 
                    versioned, parent, name, kind, executable)
806
 
 
 
1211
            if changes or include_unchanged:
 
1212
                if specific_file_ids is not None:
 
1213
                    new_parent_id = result[4][1]
 
1214
                    precise_file_ids.add(new_parent_id)
 
1215
                    changed_file_ids.append(result[0])
 
1216
                yield result
 
1217
            # Ensure correct behaviour for reparented/added specific files.
 
1218
            if specific_files is not None:
 
1219
                # Record output dirs
 
1220
                if result[6][1] == 'directory':
 
1221
                    seen_dirs.add(result[0])
 
1222
                # Record parents of reparented/added entries.
 
1223
                versioned = result[3]
 
1224
                parents = result[4]
 
1225
                if not versioned[0] or parents[0] != parents[1]:
 
1226
                    seen_parents.add(parents[1])
807
1227
        while all_unversioned:
808
1228
            # yield any trailing unversioned paths
809
1229
            unversioned_path = all_unversioned.popleft()
814
1234
                (None, unversioned_path[0][-1]),
815
1235
                (None, to_kind),
816
1236
                (None, to_executable))
817
 
 
818
 
        def get_to_path(to_entry):
819
 
            if to_entry.parent_id is None:
820
 
                to_path = '' # the root
821
 
            else:
822
 
                if to_entry.parent_id not in to_paths:
823
 
                    # recurse up
824
 
                    return get_to_path(self.target.inventory[to_entry.parent_id])
825
 
                to_path = osutils.pathjoin(to_paths[to_entry.parent_id],
826
 
                                           to_entry.name)
827
 
            to_paths[to_entry.file_id] = to_path
828
 
            return to_path
829
 
 
 
1237
        # Yield all remaining source paths
830
1238
        for path, from_entry in from_entries_by_dir:
831
1239
            file_id = from_entry.file_id
832
1240
            if file_id in to_paths:
833
1241
                # already returned
834
1242
                continue
835
 
            if not file_id in self.target.inventory:
 
1243
            if not self.target.has_id(file_id):
836
1244
                # common case - paths we have not emitted are not present in
837
1245
                # target.
838
1246
                to_path = None
839
1247
            else:
840
 
                to_path = get_to_path(self.target.inventory[file_id])
 
1248
                to_path = self.target.id2path(file_id)
841
1249
            entry_count += 1
842
1250
            if pb is not None:
843
1251
                pb.update('comparing files', entry_count, num_entries)
848
1256
                self.source._comparison_data(from_entry, path)
849
1257
            kind = (from_kind, None)
850
1258
            executable = (from_executable, None)
851
 
            changed_content = True
 
1259
            changed_content = from_kind is not None
852
1260
            # the parent's path is necessarily known at this point.
 
1261
            changed_file_ids.append(file_id)
853
1262
            yield(file_id, (path, to_path), changed_content, versioned, parent,
854
1263
                  name, kind, executable)
855
 
 
856
 
 
857
 
# This was deprecated before 0.12, but did not have an official warning
858
 
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
859
 
def RevisionTree(*args, **kwargs):
860
 
    """RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
861
 
 
862
 
    Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
863
 
    bzr 0.12.
864
 
    """
865
 
    from bzrlib.revisiontree import RevisionTree as _RevisionTree
866
 
    return _RevisionTree(*args, **kwargs)
867
 
 
868
 
 
 
1264
        changed_file_ids = set(changed_file_ids)
 
1265
        if specific_file_ids is not None:
 
1266
            for result in self._handle_precise_ids(precise_file_ids,
 
1267
                changed_file_ids):
 
1268
                yield result
 
1269
 
 
1270
    def _get_entry(self, tree, file_id):
 
1271
        """Get an inventory entry from a tree, with missing entries as None.
 
1272
 
 
1273
        If the tree raises NotImplementedError on accessing .inventory, then
 
1274
        this is worked around using iter_entries_by_dir on just the file id
 
1275
        desired.
 
1276
 
 
1277
        :param tree: The tree to lookup the entry in.
 
1278
        :param file_id: The file_id to lookup.
 
1279
        """
 
1280
        try:
 
1281
            inventory = tree.root_inventory
 
1282
        except NotImplementedError:
 
1283
            # No inventory available.
 
1284
            try:
 
1285
                iterator = tree.iter_entries_by_dir(specific_file_ids=[file_id])
 
1286
                return iterator.next()[1]
 
1287
            except StopIteration:
 
1288
                return None
 
1289
        else:
 
1290
            try:
 
1291
                return inventory[file_id]
 
1292
            except errors.NoSuchId:
 
1293
                return None
 
1294
 
 
1295
    def _handle_precise_ids(self, precise_file_ids, changed_file_ids,
 
1296
        discarded_changes=None):
 
1297
        """Fill out a partial iter_changes to be consistent.
 
1298
 
 
1299
        :param precise_file_ids: The file ids of parents that were seen during
 
1300
            the iter_changes.
 
1301
        :param changed_file_ids: The file ids of already emitted items.
 
1302
        :param discarded_changes: An optional dict of precalculated
 
1303
            iter_changes items which the partial iter_changes had not output
 
1304
            but had calculated.
 
1305
        :return: A generator of iter_changes items to output.
 
1306
        """
 
1307
        # process parents of things that had changed under the users
 
1308
        # requested paths to prevent incorrect paths or parent ids which
 
1309
        # aren't in the tree.
 
1310
        while precise_file_ids:
 
1311
            precise_file_ids.discard(None)
 
1312
            # Don't emit file_ids twice
 
1313
            precise_file_ids.difference_update(changed_file_ids)
 
1314
            if not precise_file_ids:
 
1315
                break
 
1316
            # If the there was something at a given output path in source, we
 
1317
            # have to include the entry from source in the delta, or we would
 
1318
            # be putting this entry into a used path.
 
1319
            paths = []
 
1320
            for parent_id in precise_file_ids:
 
1321
                try:
 
1322
                    paths.append(self.target.id2path(parent_id))
 
1323
                except errors.NoSuchId:
 
1324
                    # This id has been dragged in from the source by delta
 
1325
                    # expansion and isn't present in target at all: we don't
 
1326
                    # need to check for path collisions on it.
 
1327
                    pass
 
1328
            for path in paths:
 
1329
                old_id = self.source.path2id(path)
 
1330
                precise_file_ids.add(old_id)
 
1331
            precise_file_ids.discard(None)
 
1332
            current_ids = precise_file_ids
 
1333
            precise_file_ids = set()
 
1334
            # We have to emit all of precise_file_ids that have been altered.
 
1335
            # We may have to output the children of some of those ids if any
 
1336
            # directories have stopped being directories.
 
1337
            for file_id in current_ids:
 
1338
                # Examine file_id
 
1339
                if discarded_changes:
 
1340
                    result = discarded_changes.get(file_id)
 
1341
                    old_entry = None
 
1342
                else:
 
1343
                    result = None
 
1344
                if result is None:
 
1345
                    old_entry = self._get_entry(self.source, file_id)
 
1346
                    new_entry = self._get_entry(self.target, file_id)
 
1347
                    result, changes = self._changes_from_entries(
 
1348
                        old_entry, new_entry)
 
1349
                else:
 
1350
                    changes = True
 
1351
                # Get this parents parent to examine.
 
1352
                new_parent_id = result[4][1]
 
1353
                precise_file_ids.add(new_parent_id)
 
1354
                if changes:
 
1355
                    if (result[6][0] == 'directory' and
 
1356
                        result[6][1] != 'directory'):
 
1357
                        # This stopped being a directory, the old children have
 
1358
                        # to be included.
 
1359
                        if old_entry is None:
 
1360
                            # Reusing a discarded change.
 
1361
                            old_entry = self._get_entry(self.source, file_id)
 
1362
                        precise_file_ids.update(
 
1363
                                self.source.iter_children(file_id))
 
1364
                    changed_file_ids.add(result[0])
 
1365
                    yield result
 
1366
 
 
1367
    @needs_read_lock
 
1368
    def file_content_matches(self, source_file_id, target_file_id,
 
1369
            source_path=None, target_path=None, source_stat=None, target_stat=None):
 
1370
        """Check if two files are the same in the source and target trees.
 
1371
 
 
1372
        This only checks that the contents of the files are the same,
 
1373
        it does not touch anything else.
 
1374
 
 
1375
        :param source_file_id: File id of the file in the source tree
 
1376
        :param target_file_id: File id of the file in the target tree
 
1377
        :param source_path: Path of the file in the source tree
 
1378
        :param target_path: Path of the file in the target tree
 
1379
        :param source_stat: Optional stat value of the file in the source tree
 
1380
        :param target_stat: Optional stat value of the file in the target tree
 
1381
        :return: Boolean indicating whether the files have the same contents
 
1382
        """
 
1383
        source_verifier_kind, source_verifier_data = self.source.get_file_verifier(
 
1384
            source_file_id, source_path, source_stat)
 
1385
        target_verifier_kind, target_verifier_data = self.target.get_file_verifier(
 
1386
            target_file_id, target_path, target_stat)
 
1387
        if source_verifier_kind == target_verifier_kind:
 
1388
            return (source_verifier_data == target_verifier_data)
 
1389
        # Fall back to SHA1 for now
 
1390
        if source_verifier_kind != "SHA1":
 
1391
            source_sha1 = self.source.get_file_sha1(source_file_id,
 
1392
                    source_path, source_stat)
 
1393
        else:
 
1394
            source_sha1 = source_verifier_data
 
1395
        if target_verifier_kind != "SHA1":
 
1396
            target_sha1 = self.target.get_file_sha1(target_file_id,
 
1397
                    target_path, target_stat)
 
1398
        else:
 
1399
            target_sha1 = target_verifier_data
 
1400
        return (source_sha1 == target_sha1)
 
1401
 
 
1402
InterTree.register_optimiser(InterTree)
 
1403
 
 
1404
 
 
1405
class MultiWalker(object):
 
1406
    """Walk multiple trees simultaneously, getting combined results."""
 
1407
 
 
1408
    # Note: This could be written to not assume you can do out-of-order
 
1409
    #       lookups. Instead any nodes that don't match in all trees could be
 
1410
    #       marked as 'deferred', and then returned in the final cleanup loop.
 
1411
    #       For now, I think it is "nicer" to return things as close to the
 
1412
    #       "master_tree" order as we can.
 
1413
 
 
1414
    def __init__(self, master_tree, other_trees):
 
1415
        """Create a new MultiWalker.
 
1416
 
 
1417
        All trees being walked must implement "iter_entries_by_dir()", such
 
1418
        that they yield (path, object) tuples, where that object will have a
 
1419
        '.file_id' member, that can be used to check equality.
 
1420
 
 
1421
        :param master_tree: All trees will be 'slaved' to the master_tree such
 
1422
            that nodes in master_tree will be used as 'first-pass' sync points.
 
1423
            Any nodes that aren't in master_tree will be merged in a second
 
1424
            pass.
 
1425
        :param other_trees: A list of other trees to walk simultaneously.
 
1426
        """
 
1427
        self._master_tree = master_tree
 
1428
        self._other_trees = other_trees
 
1429
 
 
1430
        # Keep track of any nodes that were properly processed just out of
 
1431
        # order, that way we don't return them at the end, we don't have to
 
1432
        # track *all* processed file_ids, just the out-of-order ones
 
1433
        self._out_of_order_processed = set()
 
1434
 
 
1435
    @staticmethod
 
1436
    def _step_one(iterator):
 
1437
        """Step an iter_entries_by_dir iterator.
 
1438
 
 
1439
        :return: (has_more, path, ie)
 
1440
            If has_more is False, path and ie will be None.
 
1441
        """
 
1442
        try:
 
1443
            path, ie = iterator.next()
 
1444
        except StopIteration:
 
1445
            return False, None, None
 
1446
        else:
 
1447
            return True, path, ie
 
1448
 
 
1449
    @staticmethod
 
1450
    def _cmp_path_by_dirblock(path1, path2):
 
1451
        """Compare two paths based on what directory they are in.
 
1452
 
 
1453
        This generates a sort order, such that all children of a directory are
 
1454
        sorted together, and grandchildren are in the same order as the
 
1455
        children appear. But all grandchildren come after all children.
 
1456
 
 
1457
        :param path1: first path
 
1458
        :param path2: the second path
 
1459
        :return: negative number if ``path1`` comes first,
 
1460
            0 if paths are equal
 
1461
            and a positive number if ``path2`` sorts first
 
1462
        """
 
1463
        # Shortcut this special case
 
1464
        if path1 == path2:
 
1465
            return 0
 
1466
        # This is stolen from _dirstate_helpers_py.py, only switching it to
 
1467
        # Unicode objects. Consider using encode_utf8() and then using the
 
1468
        # optimized versions, or maybe writing optimized unicode versions.
 
1469
        if not isinstance(path1, unicode):
 
1470
            raise TypeError("'path1' must be a unicode string, not %s: %r"
 
1471
                            % (type(path1), path1))
 
1472
        if not isinstance(path2, unicode):
 
1473
            raise TypeError("'path2' must be a unicode string, not %s: %r"
 
1474
                            % (type(path2), path2))
 
1475
        return cmp(MultiWalker._path_to_key(path1),
 
1476
                   MultiWalker._path_to_key(path2))
 
1477
 
 
1478
    @staticmethod
 
1479
    def _path_to_key(path):
 
1480
        dirname, basename = osutils.split(path)
 
1481
        return (dirname.split(u'/'), basename)
 
1482
 
 
1483
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
 
1484
        """Lookup an inventory entry by file_id.
 
1485
 
 
1486
        This is called when an entry is missing in the normal order.
 
1487
        Generally this is because a file was either renamed, or it was
 
1488
        deleted/added. If the entry was found in the inventory and not in
 
1489
        extra_entries, it will be added to self._out_of_order_processed
 
1490
 
 
1491
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
 
1492
            should be filled with entries that were found before they were
 
1493
            used. If file_id is present, it will be removed from the
 
1494
            dictionary.
 
1495
        :param other_tree: The Tree to search, in case we didn't find the entry
 
1496
            yet.
 
1497
        :param file_id: The file_id to look for
 
1498
        :return: (path, ie) if found or (None, None) if not present.
 
1499
        """
 
1500
        if file_id in extra_entries:
 
1501
            return extra_entries.pop(file_id)
 
1502
        # TODO: Is id2path better as the first call, or is
 
1503
        #       inventory[file_id] better as a first check?
 
1504
        try:
 
1505
            cur_path = other_tree.id2path(file_id)
 
1506
        except errors.NoSuchId:
 
1507
            cur_path = None
 
1508
        if cur_path is None:
 
1509
            return (None, None)
 
1510
        else:
 
1511
            self._out_of_order_processed.add(file_id)
 
1512
            cur_ie = other_tree.root_inventory[file_id]
 
1513
            return (cur_path, cur_ie)
 
1514
 
 
1515
    def iter_all(self):
 
1516
        """Match up the values in the different trees."""
 
1517
        for result in self._walk_master_tree():
 
1518
            yield result
 
1519
        self._finish_others()
 
1520
        for result in self._walk_others():
 
1521
            yield result
 
1522
 
 
1523
    def _walk_master_tree(self):
 
1524
        """First pass, walk all trees in lock-step.
 
1525
 
 
1526
        When we are done, all nodes in the master_tree will have been
 
1527
        processed. _other_walkers, _other_entries, and _others_extra will be
 
1528
        set on 'self' for future processing.
 
1529
        """
 
1530
        # This iterator has the most "inlining" done, because it tends to touch
 
1531
        # every file in the tree, while the others only hit nodes that don't
 
1532
        # match.
 
1533
        master_iterator = self._master_tree.iter_entries_by_dir()
 
1534
 
 
1535
        other_walkers = [other.iter_entries_by_dir()
 
1536
                         for other in self._other_trees]
 
1537
        other_entries = [self._step_one(walker) for walker in other_walkers]
 
1538
        # Track extra nodes in the other trees
 
1539
        others_extra = [{} for i in xrange(len(self._other_trees))]
 
1540
 
 
1541
        master_has_more = True
 
1542
        step_one = self._step_one
 
1543
        lookup_by_file_id = self._lookup_by_file_id
 
1544
        out_of_order_processed = self._out_of_order_processed
 
1545
 
 
1546
        while master_has_more:
 
1547
            (master_has_more, path, master_ie) = step_one(master_iterator)
 
1548
            if not master_has_more:
 
1549
                break
 
1550
 
 
1551
            file_id = master_ie.file_id
 
1552
            other_values = []
 
1553
            other_values_append = other_values.append
 
1554
            next_other_entries = []
 
1555
            next_other_entries_append = next_other_entries.append
 
1556
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
 
1557
                if not other_has_more:
 
1558
                    other_values_append(lookup_by_file_id(
 
1559
                        others_extra[idx], self._other_trees[idx], file_id))
 
1560
                    next_other_entries_append((False, None, None))
 
1561
                elif file_id == other_ie.file_id:
 
1562
                    # This is the critical code path, as most of the entries
 
1563
                    # should match between most trees.
 
1564
                    other_values_append((other_path, other_ie))
 
1565
                    next_other_entries_append(step_one(other_walkers[idx]))
 
1566
                else:
 
1567
                    # This walker did not match, step it until it either
 
1568
                    # matches, or we know we are past the current walker.
 
1569
                    other_walker = other_walkers[idx]
 
1570
                    other_extra = others_extra[idx]
 
1571
                    while (other_has_more and
 
1572
                           self._cmp_path_by_dirblock(other_path, path) < 0):
 
1573
                        other_file_id = other_ie.file_id
 
1574
                        if other_file_id not in out_of_order_processed:
 
1575
                            other_extra[other_file_id] = (other_path, other_ie)
 
1576
                        other_has_more, other_path, other_ie = \
 
1577
                            step_one(other_walker)
 
1578
                    if other_has_more and other_ie.file_id == file_id:
 
1579
                        # We ended up walking to this point, match and step
 
1580
                        # again
 
1581
                        other_values_append((other_path, other_ie))
 
1582
                        other_has_more, other_path, other_ie = \
 
1583
                            step_one(other_walker)
 
1584
                    else:
 
1585
                        # This record isn't in the normal order, see if it
 
1586
                        # exists at all.
 
1587
                        other_values_append(lookup_by_file_id(
 
1588
                            other_extra, self._other_trees[idx], file_id))
 
1589
                    next_other_entries_append((other_has_more, other_path,
 
1590
                                               other_ie))
 
1591
            other_entries = next_other_entries
 
1592
 
 
1593
            # We've matched all the walkers, yield this datapoint
 
1594
            yield path, file_id, master_ie, other_values
 
1595
        self._other_walkers = other_walkers
 
1596
        self._other_entries = other_entries
 
1597
        self._others_extra = others_extra
 
1598
 
 
1599
    def _finish_others(self):
 
1600
        """Finish walking the other iterators, so we get all entries."""
 
1601
        for idx, info in enumerate(self._other_entries):
 
1602
            other_extra = self._others_extra[idx]
 
1603
            (other_has_more, other_path, other_ie) = info
 
1604
            while other_has_more:
 
1605
                other_file_id = other_ie.file_id
 
1606
                if other_file_id not in self._out_of_order_processed:
 
1607
                    other_extra[other_file_id] = (other_path, other_ie)
 
1608
                other_has_more, other_path, other_ie = \
 
1609
                    self._step_one(self._other_walkers[idx])
 
1610
        del self._other_entries
 
1611
 
 
1612
    def _walk_others(self):
 
1613
        """Finish up by walking all the 'deferred' nodes."""
 
1614
        # TODO: One alternative would be to grab all possible unprocessed
 
1615
        #       file_ids, and then sort by path, and then yield them. That
 
1616
        #       might ensure better ordering, in case a caller strictly
 
1617
        #       requires parents before children.
 
1618
        for idx, other_extra in enumerate(self._others_extra):
 
1619
            others = sorted(other_extra.itervalues(),
 
1620
                            key=lambda x: self._path_to_key(x[0]))
 
1621
            for other_path, other_ie in others:
 
1622
                file_id = other_ie.file_id
 
1623
                # We don't need to check out_of_order_processed here, because
 
1624
                # the lookup_by_file_id will be removing anything processed
 
1625
                # from the extras cache
 
1626
                other_extra.pop(file_id)
 
1627
                other_values = [(None, None) for i in xrange(idx)]
 
1628
                other_values.append((other_path, other_ie))
 
1629
                for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
 
1630
                    alt_idx = alt_idx + idx + 1
 
1631
                    alt_extra = self._others_extra[alt_idx]
 
1632
                    alt_tree = self._other_trees[alt_idx]
 
1633
                    other_values.append(self._lookup_by_file_id(
 
1634
                                            alt_extra, alt_tree, file_id))
 
1635
                yield other_path, file_id, None, other_values