~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

  • Committer: Ian Clatworthy
  • Date: 2009-01-19 02:24:15 UTC
  • mto: This revision was merged to the branch mainline in revision 3944.
  • Revision ID: ian.clatworthy@canonical.com-20090119022415-mo0mcfeiexfktgwt
apply jam's log --short fix (Ian Clatworthy)

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
1
# Copyright (C) 2005 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
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
 
 
7
#
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
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
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
18
"""
19
19
 
20
20
import os
 
21
from collections import deque
21
22
from cStringIO import StringIO
22
23
 
23
24
import bzrlib
 
25
from bzrlib import (
 
26
    conflicts as _mod_conflicts,
 
27
    delta,
 
28
    osutils,
 
29
    revision as _mod_revision,
 
30
    rules,
 
31
    symbol_versioning,
 
32
    )
 
33
from bzrlib.decorators import needs_read_lock
 
34
from bzrlib.errors import BzrError, BzrCheckError, NoSuchId
 
35
from bzrlib import errors
 
36
from bzrlib.inventory import Inventory, InventoryFile
 
37
from bzrlib.inter import InterObject
 
38
from bzrlib.osutils import fingerprint_file
 
39
import bzrlib.revision
 
40
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
24
41
from bzrlib.trace import mutter, note
25
 
from bzrlib.errors import BzrError, BzrCheckError
26
 
from bzrlib.inventory import Inventory
27
 
from bzrlib.osutils import fingerprint_file
 
42
 
28
43
 
29
44
class Tree(object):
30
45
    """Abstract file tree.
35
50
 
36
51
    * `RevisionTree` is a tree as recorded at some point in the past.
37
52
 
38
 
    * `EmptyTree`
39
 
 
40
53
    Trees contain an `Inventory` object, and also know how to retrieve
41
54
    file texts mentioned in the inventory, either from a working
42
55
    directory or from a store.
48
61
    trees or versioned trees.
49
62
    """
50
63
    
 
64
    def changes_from(self, other, want_unchanged=False, specific_files=None,
 
65
        extra_trees=None, require_versioned=False, include_root=False,
 
66
        want_unversioned=False):
 
67
        """Return a TreeDelta of the changes from other to this tree.
 
68
 
 
69
        :param other: A tree to compare with.
 
70
        :param specific_files: An optional list of file paths to restrict the
 
71
            comparison to. When mapping filenames to ids, all matches in all
 
72
            trees (including optional extra_trees) are used, and all children of
 
73
            matched directories are included.
 
74
        :param want_unchanged: An optional boolean requesting the inclusion of
 
75
            unchanged entries in the result.
 
76
        :param extra_trees: An optional list of additional trees to use when
 
77
            mapping the contents of specific_files (paths) to file_ids.
 
78
        :param require_versioned: An optional boolean (defaults to False). When
 
79
            supplied and True all the 'specific_files' must be versioned, or
 
80
            a PathsNotVersionedError will be thrown.
 
81
        :param want_unversioned: Scan for unversioned paths.
 
82
 
 
83
        The comparison will be performed by an InterTree object looked up on 
 
84
        self and other.
 
85
        """
 
86
        # Martin observes that Tree.changes_from returns a TreeDelta and this
 
87
        # may confuse people, because the class name of the returned object is
 
88
        # a synonym of the object referenced in the method name.
 
89
        return InterTree.get(other, self).compare(
 
90
            want_unchanged=want_unchanged,
 
91
            specific_files=specific_files,
 
92
            extra_trees=extra_trees,
 
93
            require_versioned=require_versioned,
 
94
            include_root=include_root,
 
95
            want_unversioned=want_unversioned,
 
96
            )
 
97
 
 
98
    @symbol_versioning.deprecated_method(symbol_versioning.one_three)
 
99
    def _iter_changes(self, *args, **kwargs):
 
100
        return self.iter_changes(*args, **kwargs)
 
101
 
 
102
    def iter_changes(self, from_tree, include_unchanged=False,
 
103
                     specific_files=None, pb=None, extra_trees=None,
 
104
                     require_versioned=True, want_unversioned=False):
 
105
        intertree = InterTree.get(from_tree, self)
 
106
        return intertree.iter_changes(include_unchanged, specific_files, pb,
 
107
            extra_trees, require_versioned, want_unversioned=want_unversioned)
 
108
    
 
109
    def conflicts(self):
 
110
        """Get a list of the conflicts in the tree.
 
111
 
 
112
        Each conflict is an instance of bzrlib.conflicts.Conflict.
 
113
        """
 
114
        return _mod_conflicts.ConflictList()
 
115
 
 
116
    def extras(self):
 
117
        """For trees that can have unversioned files, return all such paths."""
 
118
        return []
 
119
 
 
120
    def get_parent_ids(self):
 
121
        """Get the parent ids for this tree. 
 
122
 
 
123
        :return: a list of parent ids. [] is returned to indicate
 
124
        a tree with no parents.
 
125
        :raises: BzrError if the parents are not known.
 
126
        """
 
127
        raise NotImplementedError(self.get_parent_ids)
 
128
    
51
129
    def has_filename(self, filename):
52
130
        """True if the tree has given filename."""
53
 
        raise NotImplementedError()
 
131
        raise NotImplementedError(self.has_filename)
54
132
 
55
133
    def has_id(self, file_id):
56
134
        return self.inventory.has_id(file_id)
57
135
 
 
136
    def __contains__(self, file_id):
 
137
        return self.has_id(file_id)
 
138
 
58
139
    def has_or_had_id(self, file_id):
59
140
        if file_id == self.inventory.root.file_id:
60
141
            return True
61
142
        return self.inventory.has_id(file_id)
62
143
 
63
 
    __contains__ = has_id
 
144
    def is_ignored(self, filename):
 
145
        """Check whether the filename is ignored by this tree.
 
146
 
 
147
        :param filename: The relative filename within the tree.
 
148
        :return: True if the filename is ignored.
 
149
        """
 
150
        return False
64
151
 
65
152
    def __iter__(self):
66
153
        return iter(self.inventory)
67
154
 
 
155
    def all_file_ids(self):
 
156
        """Iterate through all file ids, including ids for missing files."""
 
157
        return set(self.inventory)
 
158
 
68
159
    def id2path(self, file_id):
 
160
        """Return the path for a file id.
 
161
 
 
162
        :raises NoSuchId:
 
163
        """
69
164
        return self.inventory.id2path(file_id)
70
165
 
 
166
    def is_control_filename(self, filename):
 
167
        """True if filename is the name of a control file in this tree.
 
168
        
 
169
        :param filename: A filename within the tree. This is a relative path
 
170
        from the root of this tree.
 
171
 
 
172
        This is true IF and ONLY IF the filename is part of the meta data
 
173
        that bzr controls in this tree. I.E. a random .bzr directory placed
 
174
        on disk will not be a control file for this tree.
 
175
        """
 
176
        return self.bzrdir.is_control_filename(filename)
 
177
 
 
178
    @needs_read_lock
 
179
    def iter_entries_by_dir(self, specific_file_ids=None):
 
180
        """Walk the tree in 'by_dir' order.
 
181
 
 
182
        This will yield each entry in the tree as a (path, entry) tuple.
 
183
        The order that they are yielded is:
 
184
 
 
185
        Directories are walked in a depth-first lexicographical order,
 
186
        however, whenever a directory is reached, all of its direct child
 
187
        nodes are yielded in  lexicographical order before yielding the
 
188
        grandchildren.
 
189
 
 
190
        For example, in the tree::
 
191
 
 
192
           a/
 
193
             b/
 
194
               c
 
195
             d/
 
196
               e
 
197
           f/
 
198
             g
 
199
 
 
200
        The yield order (ignoring root) would be::
 
201
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
 
202
        """
 
203
        return self.inventory.iter_entries_by_dir(
 
204
            specific_file_ids=specific_file_ids)
 
205
 
 
206
    def iter_references(self):
 
207
        for path, entry in self.iter_entries_by_dir():
 
208
            if entry.kind == 'tree-reference':
 
209
                yield path, entry.file_id
 
210
 
71
211
    def kind(self, file_id):
72
 
        raise NotImplementedError("subclasses must implement kind")
 
212
        raise NotImplementedError("Tree subclass %s must implement kind"
 
213
            % self.__class__.__name__)
 
214
 
 
215
    def stored_kind(self, file_id):
 
216
        """File kind stored for this file_id.
 
217
 
 
218
        May not match kind on disk for working trees.  Always available
 
219
        for versioned files, even when the file itself is missing.
 
220
        """
 
221
        return self.kind(file_id)
 
222
 
 
223
    def path_content_summary(self, path):
 
224
        """Get a summary of the information about path.
 
225
        
 
226
        :param path: A relative path within the tree.
 
227
        :return: A tuple containing kind, size, exec, sha1-or-link.
 
228
            Kind is always present (see tree.kind()).
 
229
            size is present if kind is file, None otherwise.
 
230
            exec is None unless kind is file and the platform supports the 'x'
 
231
                bit.
 
232
            sha1-or-link is the link target if kind is symlink, or the sha1 if
 
233
                it can be obtained without reading the file.
 
234
        """
 
235
        raise NotImplementedError(self.path_content_summary)
 
236
 
 
237
    def get_reference_revision(self, file_id, path=None):
 
238
        raise NotImplementedError("Tree subclass %s must implement "
 
239
                                  "get_reference_revision"
 
240
            % self.__class__.__name__)
 
241
 
 
242
    def _comparison_data(self, entry, path):
 
243
        """Return a tuple of kind, executable, stat_value for a file.
 
244
 
 
245
        entry may be None if there is no inventory entry for the file, but
 
246
        path must always be supplied.
 
247
 
 
248
        kind is None if there is no file present (even if an inventory id is
 
249
        present).  executable is False for non-file entries.
 
250
        """
 
251
        raise NotImplementedError(self._comparison_data)
 
252
 
 
253
    def _file_size(self, entry, stat_value):
 
254
        raise NotImplementedError(self._file_size)
73
255
 
74
256
    def _get_inventory(self):
75
257
        return self._inventory
76
258
    
 
259
    def get_file(self, file_id, path=None):
 
260
        """Return a file object for the file file_id in the tree.
 
261
        
 
262
        If both file_id and path are defined, it is implementation defined as
 
263
        to which one is used.
 
264
        """
 
265
        raise NotImplementedError(self.get_file)
 
266
 
 
267
    def get_file_text(self, file_id, path=None):
 
268
        """Return the byte content of a file.
 
269
 
 
270
        :param file_id: The file_id of the file.
 
271
        :param path: The path of the file.
 
272
        If both file_id and path are supplied, an implementation may use
 
273
        either one.
 
274
        """
 
275
        my_file = self.get_file(file_id, path)
 
276
        try:
 
277
            return my_file.read()
 
278
        finally:
 
279
            my_file.close()
 
280
 
 
281
    def get_file_lines(self, file_id, path=None):
 
282
        """Return the content of a file, as lines.
 
283
 
 
284
        :param file_id: The file_id of the file.
 
285
        :param path: The path of the file.
 
286
        If both file_id and path are supplied, an implementation may use
 
287
        either one.
 
288
        """
 
289
        return osutils.split_lines(self.get_file_text(file_id, path))
 
290
 
 
291
    def get_file_mtime(self, file_id, path=None):
 
292
        """Return the modification time for a file.
 
293
 
 
294
        :param file_id: The handle for this file.
 
295
        :param path: The path that this file can be found at.
 
296
            These must point to the same object.
 
297
        """
 
298
        raise NotImplementedError(self.get_file_mtime)
 
299
 
 
300
    def get_file_size(self, file_id):
 
301
        """Return the size of a file in bytes.
 
302
 
 
303
        This applies only to regular files.  If invoked on directories or
 
304
        symlinks, it will return None.
 
305
        :param file_id: The file-id of the file
 
306
        """
 
307
        raise NotImplementedError(self.get_file_size)
 
308
 
77
309
    def get_file_by_path(self, path):
78
 
        return self.get_file(self._inventory.path2id(path))
 
310
        return self.get_file(self._inventory.path2id(path), path)
 
311
 
 
312
    def iter_files_bytes(self, desired_files):
 
313
        """Iterate through file contents.
 
314
 
 
315
        Files will not necessarily be returned in the order they occur in
 
316
        desired_files.  No specific order is guaranteed.
 
317
 
 
318
        Yields pairs of identifier, bytes_iterator.  identifier is an opaque
 
319
        value supplied by the caller as part of desired_files.  It should
 
320
        uniquely identify the file version in the caller's context.  (Examples:
 
321
        an index number or a TreeTransform trans_id.)
 
322
 
 
323
        bytes_iterator is an iterable of bytestrings for the file.  The
 
324
        kind of iterable and length of the bytestrings are unspecified, but for
 
325
        this implementation, it is a tuple containing a single bytestring with
 
326
        the complete text of the file.
 
327
 
 
328
        :param desired_files: a list of (file_id, identifier) pairs
 
329
        """
 
330
        for file_id, identifier in desired_files:
 
331
            # We wrap the string in a tuple so that we can return an iterable
 
332
            # of bytestrings.  (Technically, a bytestring is also an iterable
 
333
            # of bytestrings, but iterating through each character is not
 
334
            # performant.)
 
335
            cur_file = (self.get_file_text(file_id),)
 
336
            yield identifier, cur_file
 
337
 
 
338
    def get_symlink_target(self, file_id):
 
339
        """Get the target for a given file_id.
 
340
 
 
341
        It is assumed that the caller already knows that file_id is referencing
 
342
        a symlink.
 
343
        :param file_id: Handle for the symlink entry.
 
344
        :return: The path the symlink points to.
 
345
        """
 
346
        raise NotImplementedError(self.get_symlink_target)
 
347
 
 
348
    def get_canonical_inventory_paths(self, paths):
 
349
        """Like get_canonical_inventory_path() but works on multiple items.
 
350
 
 
351
        :param paths: A sequence of paths relative to the root of the tree.
 
352
        :return: A list of paths, with each item the corresponding input path
 
353
        adjusted to account for existing elements that match case
 
354
        insensitively.
 
355
        """
 
356
        return list(self._yield_canonical_inventory_paths(paths))
 
357
 
 
358
    def get_canonical_inventory_path(self, path):
 
359
        """Returns the first inventory item that case-insensitively matches path.
 
360
 
 
361
        If a path matches exactly, it is returned. If no path matches exactly
 
362
        but more than one path matches case-insensitively, it is implementation
 
363
        defined which is returned.
 
364
 
 
365
        If no path matches case-insensitively, the input path is returned, but
 
366
        with as many path entries that do exist changed to their canonical
 
367
        form.
 
368
 
 
369
        If you need to resolve many names from the same tree, you should
 
370
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
371
 
 
372
        :param path: A paths relative to the root of the tree.
 
373
        :return: The input path adjusted to account for existing elements
 
374
        that match case insensitively.
 
375
        """
 
376
        return self._yield_canonical_inventory_paths([path]).next()
 
377
 
 
378
    def _yield_canonical_inventory_paths(self, paths):
 
379
        for path in paths:
 
380
            # First, if the path as specified exists exactly, just use it.
 
381
            if self.path2id(path) is not None:
 
382
                yield path
 
383
                continue
 
384
            # go walkin...
 
385
            cur_id = self.get_root_id()
 
386
            cur_path = ''
 
387
            bit_iter = iter(path.split("/"))
 
388
            for elt in bit_iter:
 
389
                lelt = elt.lower()
 
390
                for child in self.iter_children(cur_id):
 
391
                    try:
 
392
                        child_base = os.path.basename(self.id2path(child))
 
393
                        if child_base.lower() == lelt:
 
394
                            cur_id = child
 
395
                            cur_path = osutils.pathjoin(cur_path, child_base)
 
396
                            break
 
397
                    except NoSuchId:
 
398
                        # before a change is committed we can see this error...
 
399
                        continue
 
400
                else:
 
401
                    # got to the end of this directory and no entries matched.
 
402
                    # Return what matched so far, plus the rest as specified.
 
403
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
404
                    break
 
405
            yield cur_path
 
406
        # all done.
 
407
 
 
408
    def get_root_id(self):
 
409
        """Return the file_id for the root of this tree."""
 
410
        raise NotImplementedError(self.get_root_id)
 
411
 
 
412
    def annotate_iter(self, file_id,
 
413
                      default_revision=_mod_revision.CURRENT_REVISION):
 
414
        """Return an iterator of revision_id, line tuples.
 
415
 
 
416
        For working trees (and mutable trees in general), the special
 
417
        revision_id 'current:' will be used for lines that are new in this
 
418
        tree, e.g. uncommitted changes.
 
419
        :param file_id: The file to produce an annotated version from
 
420
        :param default_revision: For lines that don't match a basis, mark them
 
421
            with this revision id. Not all implementations will make use of
 
422
            this value.
 
423
        """
 
424
        raise NotImplementedError(self.annotate_iter)
 
425
 
 
426
    def _get_plan_merge_data(self, file_id, other, base):
 
427
        from bzrlib import merge, versionedfile
 
428
        vf = versionedfile._PlanMergeVersionedFile(file_id)
 
429
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
 
430
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
 
431
        if base is None:
 
432
            last_revision_base = None
 
433
        else:
 
434
            last_revision_base = base._get_file_revision(file_id, vf, 'base:')
 
435
        return vf, last_revision_a, last_revision_b, last_revision_base
 
436
 
 
437
    def plan_file_merge(self, file_id, other, base=None):
 
438
        """Generate a merge plan based on annotations.
 
439
 
 
440
        If the file contains uncommitted changes in this tree, they will be
 
441
        attributed to the 'current:' pseudo-revision.  If the file contains
 
442
        uncommitted changes in the other tree, they will be assigned to the
 
443
        'other:' pseudo-revision.
 
444
        """
 
445
        data = self._get_plan_merge_data(file_id, other, base)
 
446
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
447
        return vf.plan_merge(last_revision_a, last_revision_b,
 
448
                             last_revision_base)
 
449
 
 
450
    def plan_file_lca_merge(self, file_id, other, base=None):
 
451
        """Generate a merge plan based lca-newness.
 
452
 
 
453
        If the file contains uncommitted changes in this tree, they will be
 
454
        attributed to the 'current:' pseudo-revision.  If the file contains
 
455
        uncommitted changes in the other tree, they will be assigned to the
 
456
        'other:' pseudo-revision.
 
457
        """
 
458
        data = self._get_plan_merge_data(file_id, other, base)
 
459
        vf, last_revision_a, last_revision_b, last_revision_base = data
 
460
        return vf.plan_lca_merge(last_revision_a, last_revision_b,
 
461
                                 last_revision_base)
 
462
 
 
463
    def _iter_parent_trees(self):
 
464
        """Iterate through parent trees, defaulting to Tree.revision_tree."""
 
465
        for revision_id in self.get_parent_ids():
 
466
            try:
 
467
                yield self.revision_tree(revision_id)
 
468
            except errors.NoSuchRevisionInTree:
 
469
                yield self.repository.revision_tree(revision_id)
 
470
 
 
471
    @staticmethod
 
472
    def _file_revision(revision_tree, file_id):
 
473
        """Determine the revision associated with a file in a given tree."""
 
474
        revision_tree.lock_read()
 
475
        try:
 
476
            return revision_tree.inventory[file_id].revision
 
477
        finally:
 
478
            revision_tree.unlock()
 
479
 
 
480
    def _get_file_revision(self, file_id, vf, tree_revision):
 
481
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
 
482
 
 
483
        if getattr(self, '_repository', None) is None:
 
484
            last_revision = tree_revision
 
485
            parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
 
486
                self._iter_parent_trees()]
 
487
            vf.add_lines((file_id, last_revision), parent_keys,
 
488
                         self.get_file(file_id).readlines())
 
489
            repo = self.branch.repository
 
490
            base_vf = repo.texts
 
491
        else:
 
492
            last_revision = self._file_revision(self, file_id)
 
493
            base_vf = self._repository.texts
 
494
        if base_vf not in vf.fallback_versionedfiles:
 
495
            vf.fallback_versionedfiles.append(base_vf)
 
496
        return last_revision
79
497
 
80
498
    inventory = property(_get_inventory,
81
499
                         doc="Inventory of this Tree")
86
504
        fp = fingerprint_file(f)
87
505
        f.seek(0)
88
506
        
89
 
        if ie.text_size != None:
 
507
        if ie.text_size is not None:
90
508
            if ie.text_size != fp['size']:
91
509
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
92
510
                        ["inventory expects %d bytes" % ie.text_size,
99
517
                     "file is actually %s" % fp['sha1'],
100
518
                     "store is probably damaged/corrupt"])
101
519
 
102
 
 
 
520
    @needs_read_lock
 
521
    def path2id(self, path):
 
522
        """Return the id for path in this tree."""
 
523
        return self._inventory.path2id(path)
 
524
 
 
525
    def paths2ids(self, paths, trees=[], require_versioned=True):
 
526
        """Return all the ids that can be reached by walking from paths.
 
527
        
 
528
        Each path is looked up in this tree and any extras provided in
 
529
        trees, and this is repeated recursively: the children in an extra tree
 
530
        of a directory that has been renamed under a provided path in this tree
 
531
        are all returned, even if none exist under a provided path in this
 
532
        tree, and vice versa.
 
533
 
 
534
        :param paths: An iterable of paths to start converting to ids from.
 
535
            Alternatively, if paths is None, no ids should be calculated and None
 
536
            will be returned. This is offered to make calling the api unconditional
 
537
            for code that *might* take a list of files.
 
538
        :param trees: Additional trees to consider.
 
539
        :param require_versioned: If False, do not raise NotVersionedError if
 
540
            an element of paths is not versioned in this tree and all of trees.
 
541
        """
 
542
        return find_ids_across_trees(paths, [self] + list(trees), require_versioned)
 
543
 
 
544
    def iter_children(self, file_id):
 
545
        entry = self.iter_entries_by_dir([file_id]).next()[1]
 
546
        for child in getattr(entry, 'children', {}).itervalues():
 
547
            yield child.file_id
 
548
 
 
549
    @symbol_versioning.deprecated_method(symbol_versioning.one_six)
103
550
    def print_file(self, file_id):
104
551
        """Print file with id `file_id` to stdout."""
105
552
        import sys
108
555
    def lock_read(self):
109
556
        pass
110
557
 
 
558
    def revision_tree(self, revision_id):
 
559
        """Obtain a revision tree for the revision revision_id.
 
560
 
 
561
        The intention of this method is to allow access to possibly cached
 
562
        tree data. Implementors of this method should raise NoSuchRevision if
 
563
        the tree is not locally available, even if they could obtain the 
 
564
        tree via a repository or some other means. Callers are responsible 
 
565
        for finding the ultimate source for a revision tree.
 
566
 
 
567
        :param revision_id: The revision_id of the requested tree.
 
568
        :return: A Tree.
 
569
        :raises: NoSuchRevision if the tree cannot be obtained.
 
570
        """
 
571
        raise errors.NoSuchRevisionInTree(self, revision_id)
 
572
 
 
573
    def unknowns(self):
 
574
        """What files are present in this tree and unknown.
 
575
        
 
576
        :return: an iterator over the unknown files.
 
577
        """
 
578
        return iter([])
 
579
 
111
580
    def unlock(self):
112
581
        pass
113
582
 
114
583
    def filter_unversioned_files(self, paths):
115
 
        """Filter out paths that are not versioned.
 
584
        """Filter out paths that are versioned.
116
585
 
117
586
        :return: set of paths.
118
587
        """
121
590
        # are not versioned.
122
591
        pred = self.inventory.has_filename
123
592
        return set((p for p in paths if not pred(p)))
124
 
        
125
 
        
126
 
class RevisionTree(Tree):
127
 
    """Tree viewing a previous revision.
128
 
 
129
 
    File text can be retrieved from the text store.
130
 
 
131
 
    TODO: Some kind of `__repr__` method, but a good one
132
 
           probably means knowing the branch and revision number,
133
 
           or at least passing a description to the constructor.
134
 
    """
135
 
    
136
 
    def __init__(self, branch, inv, revision_id):
137
 
        self._branch = branch
138
 
        self._weave_store = branch.weave_store
139
 
        self._inventory = inv
140
 
        self._revision_id = revision_id
141
 
 
142
 
    def get_revision_id(self):
143
 
        """Return the revision id associated with this tree."""
144
 
        return self._revision_id
145
 
 
146
 
    def get_weave(self, file_id):
147
 
        return self._weave_store.get_weave(file_id,
148
 
                self._branch.get_transaction())
149
 
 
150
 
    def get_file_lines(self, file_id):
151
 
        ie = self._inventory[file_id]
152
 
        weave = self.get_weave(file_id)
153
 
        return weave.get_lines(ie.revision)
154
 
 
155
 
    def get_file_text(self, file_id):
156
 
        return ''.join(self.get_file_lines(file_id))
157
 
 
158
 
    def get_file(self, file_id):
159
 
        return StringIO(self.get_file_text(file_id))
160
 
 
161
 
    def get_file_size(self, file_id):
162
 
        return self._inventory[file_id].text_size
163
 
 
164
 
    def get_file_sha1(self, file_id, path=None):
165
 
        ie = self._inventory[file_id]
166
 
        if ie.kind == "file":
167
 
            return ie.text_sha1
168
 
        return None
169
 
 
170
 
    def get_file_mtime(self, file_id, path=None):
171
 
        ie = self._inventory[file_id]
172
 
        revision = self._branch.get_revision(ie.revision)
173
 
        return revision.timestamp
174
 
 
175
 
    def is_executable(self, file_id, path=None):
176
 
        ie = self._inventory[file_id]
177
 
        if ie.kind != "file":
178
 
            return None 
179
 
        return self._inventory[file_id].executable
180
 
 
181
 
    def has_filename(self, filename):
182
 
        return bool(self.inventory.path2id(filename))
183
 
 
184
 
    def list_files(self):
185
 
        # The only files returned by this are those from the version
186
 
        for path, entry in self.inventory.iter_entries():
187
 
            yield path, 'V', entry.kind, entry.file_id, entry
188
 
 
189
 
    def get_symlink_target(self, file_id):
190
 
        ie = self._inventory[file_id]
191
 
        return ie.symlink_target;
192
 
 
193
 
    def kind(self, file_id):
194
 
        return self._inventory[file_id].kind
195
 
 
196
 
    def lock_read(self):
197
 
        self._branch.lock_read()
198
 
 
199
 
    def unlock(self):
200
 
        self._branch.unlock()
 
593
 
 
594
    def walkdirs(self, prefix=""):
 
595
        """Walk the contents of this tree from path down.
 
596
 
 
597
        This yields all the data about the contents of a directory at a time.
 
598
        After each directory has been yielded, if the caller has mutated the
 
599
        list to exclude some directories, they are then not descended into.
 
600
        
 
601
        The data yielded is of the form:
 
602
        ((directory-relpath, directory-path-from-root, directory-fileid),
 
603
        [(relpath, basename, kind, lstat, path_from_tree_root, file_id, 
 
604
          versioned_kind), ...]),
 
605
         - directory-relpath is the containing dirs relpath from prefix
 
606
         - directory-path-from-root is the containing dirs path from /
 
607
         - directory-fileid is the id of the directory if it is versioned.
 
608
         - relpath is the relative path within the subtree being walked.
 
609
         - basename is the basename
 
610
         - kind is the kind of the file now. If unknonwn then the file is not
 
611
           present within the tree - but it may be recorded as versioned. See
 
612
           versioned_kind.
 
613
         - lstat is the stat data *if* the file was statted.
 
614
         - path_from_tree_root is the path from the root of the tree.
 
615
         - file_id is the file_id if the entry is versioned.
 
616
         - versioned_kind is the kind of the file as last recorded in the 
 
617
           versioning system. If 'unknown' the file is not versioned.
 
618
        One of 'kind' and 'versioned_kind' must not be 'unknown'.
 
619
 
 
620
        :param prefix: Start walking from prefix within the tree rather than
 
621
        at the root. This allows one to walk a subtree but get paths that are
 
622
        relative to a tree rooted higher up.
 
623
        :return: an iterator over the directory data.
 
624
        """
 
625
        raise NotImplementedError(self.walkdirs)
 
626
 
 
627
    def supports_content_filtering(self):
 
628
        return False
 
629
 
 
630
    def iter_search_rules(self, path_names, pref_names=None,
 
631
        _default_searcher=rules._per_user_searcher):
 
632
        """Find the preferences for filenames in a tree.
 
633
 
 
634
        :param path_names: an iterable of paths to find attributes for.
 
635
          Paths are given relative to the root of the tree.
 
636
        :param pref_names: the list of preferences to lookup - None for all
 
637
        :param _default_searcher: private parameter to assist testing - don't use
 
638
        :return: an iterator of tuple sequences, one per path-name.
 
639
          See _RulesSearcher.get_items for details on the tuple sequence.
 
640
        """
 
641
        searcher = self._get_rules_searcher(_default_searcher)
 
642
        if searcher is not None:
 
643
            if pref_names is not None:
 
644
                for path in path_names:
 
645
                    yield searcher.get_selected_items(path, pref_names)
 
646
            else:
 
647
                for path in path_names:
 
648
                    yield searcher.get_items(path)
 
649
 
 
650
    @needs_read_lock
 
651
    def _get_rules_searcher(self, default_searcher):
 
652
        """Get the RulesSearcher for this tree given the default one."""
 
653
        searcher = default_searcher
 
654
        return searcher
201
655
 
202
656
 
203
657
class EmptyTree(Tree):
 
658
 
204
659
    def __init__(self):
205
 
        self._inventory = Inventory()
 
660
        self._inventory = Inventory(root_id=None)
 
661
        symbol_versioning.warn('EmptyTree is deprecated as of bzr 0.9 please'
 
662
                               ' use repository.revision_tree instead.',
 
663
                               DeprecationWarning, stacklevel=2)
 
664
 
 
665
    def get_parent_ids(self):
 
666
        return []
206
667
 
207
668
    def get_symlink_target(self, file_id):
208
669
        return None
211
672
        return False
212
673
 
213
674
    def kind(self, file_id):
214
 
        assert self._inventory[file_id].kind == "root_directory"
215
 
        return "root_directory"
 
675
        return "directory"
216
676
 
217
 
    def list_files(self):
 
677
    def list_files(self, include_root=False):
218
678
        return iter([])
219
679
    
220
680
    def __contains__(self, file_id):
221
 
        return file_id in self._inventory
 
681
        return (file_id in self._inventory)
222
682
 
223
 
    def get_file_sha1(self, file_id, path=None):
224
 
        assert self._inventory[file_id].kind == "root_directory"
 
683
    def get_file_sha1(self, file_id, path=None, stat_value=None):
225
684
        return None
226
685
 
227
686
 
261
720
        # what happened to the file that used to have
262
721
        # this name.  There are two possibilities: either it was
263
722
        # deleted entirely, or renamed.
264
 
        assert old_id
265
723
        if new_inv.has_id(old_id):
266
724
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
267
725
        else:
279
737
    return 'wtf?'
280
738
 
281
739
    
282
 
 
 
740
@deprecated_function(deprecated_in((1, 9, 0)))
283
741
def find_renames(old_inv, new_inv):
284
742
    for file_id in old_inv:
285
743
        if file_id not in new_inv:
288
746
        new_name = new_inv.id2path(file_id)
289
747
        if old_name != new_name:
290
748
            yield (old_name, new_name)
291
 
            
292
 
 
293
 
 
 
749
 
 
750
 
 
751
def find_ids_across_trees(filenames, trees, require_versioned=True):
 
752
    """Find the ids corresponding to specified filenames.
 
753
    
 
754
    All matches in all trees will be used, and all children of matched
 
755
    directories will be used.
 
756
 
 
757
    :param filenames: The filenames to find file_ids for (if None, returns
 
758
        None)
 
759
    :param trees: The trees to find file_ids within
 
760
    :param require_versioned: if true, all specified filenames must occur in
 
761
    at least one tree.
 
762
    :return: a set of file ids for the specified filenames and their children.
 
763
    """
 
764
    if not filenames:
 
765
        return None
 
766
    specified_path_ids = _find_ids_across_trees(filenames, trees,
 
767
        require_versioned)
 
768
    return _find_children_across_trees(specified_path_ids, trees)
 
769
 
 
770
 
 
771
def _find_ids_across_trees(filenames, trees, require_versioned):
 
772
    """Find the ids corresponding to specified filenames.
 
773
    
 
774
    All matches in all trees will be used, but subdirectories are not scanned.
 
775
 
 
776
    :param filenames: The filenames to find file_ids for
 
777
    :param trees: The trees to find file_ids within
 
778
    :param require_versioned: if true, all specified filenames must occur in
 
779
        at least one tree.
 
780
    :return: a set of file ids for the specified filenames
 
781
    """
 
782
    not_versioned = []
 
783
    interesting_ids = set()
 
784
    for tree_path in filenames:
 
785
        not_found = True
 
786
        for tree in trees:
 
787
            file_id = tree.path2id(tree_path)
 
788
            if file_id is not None:
 
789
                interesting_ids.add(file_id)
 
790
                not_found = False
 
791
        if not_found:
 
792
            not_versioned.append(tree_path)
 
793
    if len(not_versioned) > 0 and require_versioned:
 
794
        raise errors.PathsNotVersionedError(not_versioned)
 
795
    return interesting_ids
 
796
 
 
797
 
 
798
def _find_children_across_trees(specified_ids, trees):
 
799
    """Return a set including specified ids and their children.
 
800
    
 
801
    All matches in all trees will be used.
 
802
 
 
803
    :param trees: The trees to find file_ids within
 
804
    :return: a set containing all specified ids and their children 
 
805
    """
 
806
    interesting_ids = set(specified_ids)
 
807
    pending = interesting_ids
 
808
    # now handle children of interesting ids
 
809
    # we loop so that we handle all children of each id in both trees
 
810
    while len(pending) > 0:
 
811
        new_pending = set()
 
812
        for file_id in pending:
 
813
            for tree in trees:
 
814
                if not tree.has_id(file_id):
 
815
                    continue
 
816
                for child_id in tree.iter_children(file_id):
 
817
                    if child_id not in interesting_ids:
 
818
                        new_pending.add(child_id)
 
819
        interesting_ids.update(new_pending)
 
820
        pending = new_pending
 
821
    return interesting_ids
 
822
 
 
823
 
 
824
class InterTree(InterObject):
 
825
    """This class represents operations taking place between two Trees.
 
826
 
 
827
    Its instances have methods like 'compare' and contain references to the
 
828
    source and target trees these operations are to be carried out on.
 
829
 
 
830
    Clients of bzrlib should not need to use InterTree directly, rather they
 
831
    should use the convenience methods on Tree such as 'Tree.compare()' which
 
832
    will pass through to InterTree as appropriate.
 
833
    """
 
834
 
 
835
    _optimisers = []
 
836
 
 
837
    @needs_read_lock
 
838
    def compare(self, want_unchanged=False, specific_files=None,
 
839
        extra_trees=None, require_versioned=False, include_root=False,
 
840
        want_unversioned=False):
 
841
        """Return the changes from source to target.
 
842
 
 
843
        :return: A TreeDelta.
 
844
        :param specific_files: An optional list of file paths to restrict the
 
845
            comparison to. When mapping filenames to ids, all matches in all
 
846
            trees (including optional extra_trees) are used, and all children of
 
847
            matched directories are included.
 
848
        :param want_unchanged: An optional boolean requesting the inclusion of
 
849
            unchanged entries in the result.
 
850
        :param extra_trees: An optional list of additional trees to use when
 
851
            mapping the contents of specific_files (paths) to file_ids.
 
852
        :param require_versioned: An optional boolean (defaults to False). When
 
853
            supplied and True all the 'specific_files' must be versioned, or
 
854
            a PathsNotVersionedError will be thrown.
 
855
        :param want_unversioned: Scan for unversioned paths.
 
856
        """
 
857
        # NB: show_status depends on being able to pass in non-versioned files
 
858
        # and report them as unknown
 
859
        trees = (self.source,)
 
860
        if extra_trees is not None:
 
861
            trees = trees + tuple(extra_trees)
 
862
        # target is usually the newer tree:
 
863
        specific_file_ids = self.target.paths2ids(specific_files, trees,
 
864
            require_versioned=require_versioned)
 
865
        if specific_files and not specific_file_ids:
 
866
            # All files are unversioned, so just return an empty delta
 
867
            # _compare_trees would think we want a complete delta
 
868
            result = delta.TreeDelta()
 
869
            fake_entry = InventoryFile('unused', 'unused', 'unused')
 
870
            result.unversioned = [(path, None,
 
871
                self.target._comparison_data(fake_entry, path)[0]) for path in
 
872
                specific_files]
 
873
            return result
 
874
        return delta._compare_trees(self.source, self.target, want_unchanged,
 
875
            specific_files, include_root, extra_trees=extra_trees,
 
876
            require_versioned=require_versioned,
 
877
            want_unversioned=want_unversioned)
 
878
 
 
879
    def iter_changes(self, include_unchanged=False,
 
880
                      specific_files=None, pb=None, extra_trees=[],
 
881
                      require_versioned=True, want_unversioned=False):
 
882
        """Generate an iterator of changes between trees.
 
883
 
 
884
        A tuple is returned:
 
885
        (file_id, (path_in_source, path_in_target),
 
886
         changed_content, versioned, parent, name, kind,
 
887
         executable)
 
888
 
 
889
        Changed_content is True if the file's content has changed.  This
 
890
        includes changes to its kind, and to a symlink's target.
 
891
 
 
892
        versioned, parent, name, kind, executable are tuples of (from, to).
 
893
        If a file is missing in a tree, its kind is None.
 
894
 
 
895
        Iteration is done in parent-to-child order, relative to the target
 
896
        tree.
 
897
 
 
898
        There is no guarantee that all paths are in sorted order: the
 
899
        requirement to expand the search due to renames may result in children
 
900
        that should be found early being found late in the search, after
 
901
        lexically later results have been returned.
 
902
        :param require_versioned: Raise errors.PathsNotVersionedError if a
 
903
            path in the specific_files list is not versioned in one of
 
904
            source, target or extra_trees.
 
905
        :param want_unversioned: Should unversioned files be returned in the
 
906
            output. An unversioned file is defined as one with (False, False)
 
907
            for the versioned pair.
 
908
        """
 
909
        result = []
 
910
        lookup_trees = [self.source]
 
911
        if extra_trees:
 
912
             lookup_trees.extend(extra_trees)
 
913
        if specific_files == []:
 
914
            specific_file_ids = []
 
915
        else:
 
916
            specific_file_ids = self.target.paths2ids(specific_files,
 
917
                lookup_trees, require_versioned=require_versioned)
 
918
        if want_unversioned:
 
919
            all_unversioned = sorted([(p.split('/'), p) for p in
 
920
                                     self.target.extras()
 
921
                if specific_files is None or
 
922
                    osutils.is_inside_any(specific_files, p)])
 
923
            all_unversioned = deque(all_unversioned)
 
924
        else:
 
925
            all_unversioned = deque()
 
926
        to_paths = {}
 
927
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
 
928
            specific_file_ids=specific_file_ids))
 
929
        from_data = dict((e.file_id, (p, e)) for p, e in from_entries_by_dir)
 
930
        to_entries_by_dir = list(self.target.iter_entries_by_dir(
 
931
            specific_file_ids=specific_file_ids))
 
932
        num_entries = len(from_entries_by_dir) + len(to_entries_by_dir)
 
933
        entry_count = 0
 
934
        # the unversioned path lookup only occurs on real trees - where there 
 
935
        # can be extras. So the fake_entry is solely used to look up
 
936
        # executable it values when execute is not supported.
 
937
        fake_entry = InventoryFile('unused', 'unused', 'unused')
 
938
        for to_path, to_entry in to_entries_by_dir:
 
939
            while all_unversioned and all_unversioned[0][0] < to_path.split('/'):
 
940
                unversioned_path = all_unversioned.popleft()
 
941
                to_kind, to_executable, to_stat = \
 
942
                    self.target._comparison_data(fake_entry, unversioned_path[1])
 
943
                yield (None, (None, unversioned_path[1]), True, (False, False),
 
944
                    (None, None),
 
945
                    (None, unversioned_path[0][-1]),
 
946
                    (None, to_kind),
 
947
                    (None, to_executable))
 
948
            file_id = to_entry.file_id
 
949
            to_paths[file_id] = to_path
 
950
            entry_count += 1
 
951
            changed_content = False
 
952
            from_path, from_entry = from_data.get(file_id, (None, None))
 
953
            from_versioned = (from_entry is not None)
 
954
            if from_entry is not None:
 
955
                from_versioned = True
 
956
                from_name = from_entry.name
 
957
                from_parent = from_entry.parent_id
 
958
                from_kind, from_executable, from_stat = \
 
959
                    self.source._comparison_data(from_entry, from_path)
 
960
                entry_count += 1
 
961
            else:
 
962
                from_versioned = False
 
963
                from_kind = None
 
964
                from_parent = None
 
965
                from_name = None
 
966
                from_executable = None
 
967
            versioned = (from_versioned, True)
 
968
            to_kind, to_executable, to_stat = \
 
969
                self.target._comparison_data(to_entry, to_path)
 
970
            kind = (from_kind, to_kind)
 
971
            if kind[0] != kind[1]:
 
972
                changed_content = True
 
973
            elif from_kind == 'file':
 
974
                from_size = self.source._file_size(from_entry, from_stat)
 
975
                to_size = self.target._file_size(to_entry, to_stat)
 
976
                if from_size != to_size:
 
977
                    changed_content = True
 
978
                elif (self.source.get_file_sha1(file_id, from_path, from_stat) !=
 
979
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
 
980
                    changed_content = True
 
981
            elif from_kind == 'symlink':
 
982
                if (self.source.get_symlink_target(file_id) !=
 
983
                    self.target.get_symlink_target(file_id)):
 
984
                    changed_content = True
 
985
                elif from_kind == 'tree-reference':
 
986
                    if (self.source.get_reference_revision(file_id, from_path)
 
987
                        != self.target.get_reference_revision(file_id, to_path)):
 
988
                        changed_content = True 
 
989
            parent = (from_parent, to_entry.parent_id)
 
990
            name = (from_name, to_entry.name)
 
991
            executable = (from_executable, to_executable)
 
992
            if pb is not None:
 
993
                pb.update('comparing files', entry_count, num_entries)
 
994
            if (changed_content is not False or versioned[0] != versioned[1]
 
995
                or parent[0] != parent[1] or name[0] != name[1] or 
 
996
                executable[0] != executable[1] or include_unchanged):
 
997
                yield (file_id, (from_path, to_path), changed_content,
 
998
                    versioned, parent, name, kind, executable)
 
999
 
 
1000
        while all_unversioned:
 
1001
            # yield any trailing unversioned paths
 
1002
            unversioned_path = all_unversioned.popleft()
 
1003
            to_kind, to_executable, to_stat = \
 
1004
                self.target._comparison_data(fake_entry, unversioned_path[1])
 
1005
            yield (None, (None, unversioned_path[1]), True, (False, False),
 
1006
                (None, None),
 
1007
                (None, unversioned_path[0][-1]),
 
1008
                (None, to_kind),
 
1009
                (None, to_executable))
 
1010
 
 
1011
        def get_to_path(to_entry):
 
1012
            if to_entry.parent_id is None:
 
1013
                to_path = '' # the root
 
1014
            else:
 
1015
                if to_entry.parent_id not in to_paths:
 
1016
                    # recurse up
 
1017
                    return get_to_path(self.target.inventory[to_entry.parent_id])
 
1018
                to_path = osutils.pathjoin(to_paths[to_entry.parent_id],
 
1019
                                           to_entry.name)
 
1020
            to_paths[to_entry.file_id] = to_path
 
1021
            return to_path
 
1022
 
 
1023
        for path, from_entry in from_entries_by_dir:
 
1024
            file_id = from_entry.file_id
 
1025
            if file_id in to_paths:
 
1026
                # already returned
 
1027
                continue
 
1028
            if not file_id in self.target.all_file_ids():
 
1029
                # common case - paths we have not emitted are not present in
 
1030
                # target.
 
1031
                to_path = None
 
1032
            else:
 
1033
                to_path = get_to_path(self.target.inventory[file_id])
 
1034
            entry_count += 1
 
1035
            if pb is not None:
 
1036
                pb.update('comparing files', entry_count, num_entries)
 
1037
            versioned = (True, False)
 
1038
            parent = (from_entry.parent_id, None)
 
1039
            name = (from_entry.name, None)
 
1040
            from_kind, from_executable, stat_value = \
 
1041
                self.source._comparison_data(from_entry, path)
 
1042
            kind = (from_kind, None)
 
1043
            executable = (from_executable, None)
 
1044
            changed_content = from_kind is not None
 
1045
            # the parent's path is necessarily known at this point.
 
1046
            yield(file_id, (path, to_path), changed_content, versioned, parent,
 
1047
                  name, kind, executable)
 
1048
 
 
1049
 
 
1050
class MultiWalker(object):
 
1051
    """Walk multiple trees simultaneously, getting combined results."""
 
1052
 
 
1053
    # Note: This could be written to not assume you can do out-of-order
 
1054
    #       lookups. Instead any nodes that don't match in all trees could be
 
1055
    #       marked as 'deferred', and then returned in the final cleanup loop.
 
1056
    #       For now, I think it is "nicer" to return things as close to the
 
1057
    #       "master_tree" order as we can.
 
1058
 
 
1059
    def __init__(self, master_tree, other_trees):
 
1060
        """Create a new MultiWalker.
 
1061
 
 
1062
        All trees being walked must implement "iter_entries_by_dir()", such
 
1063
        that they yield (path, object) tuples, where that object will have a
 
1064
        '.file_id' member, that can be used to check equality.
 
1065
 
 
1066
        :param master_tree: All trees will be 'slaved' to the master_tree such
 
1067
            that nodes in master_tree will be used as 'first-pass' sync points.
 
1068
            Any nodes that aren't in master_tree will be merged in a second
 
1069
            pass.
 
1070
        :param other_trees: A list of other trees to walk simultaneously.
 
1071
        """
 
1072
        self._master_tree = master_tree
 
1073
        self._other_trees = other_trees
 
1074
 
 
1075
        # Keep track of any nodes that were properly processed just out of
 
1076
        # order, that way we don't return them at the end, we don't have to
 
1077
        # track *all* processed file_ids, just the out-of-order ones
 
1078
        self._out_of_order_processed = set()
 
1079
 
 
1080
    @staticmethod
 
1081
    def _step_one(iterator):
 
1082
        """Step an iter_entries_by_dir iterator.
 
1083
 
 
1084
        :return: (has_more, path, ie)
 
1085
            If has_more is False, path and ie will be None.
 
1086
        """
 
1087
        try:
 
1088
            path, ie = iterator.next()
 
1089
        except StopIteration:
 
1090
            return False, None, None
 
1091
        else:
 
1092
            return True, path, ie
 
1093
 
 
1094
    @staticmethod
 
1095
    def _cmp_path_by_dirblock(path1, path2):
 
1096
        """Compare two paths based on what directory they are in.
 
1097
 
 
1098
        This generates a sort order, such that all children of a directory are
 
1099
        sorted together, and grandchildren are in the same order as the
 
1100
        children appear. But all grandchildren come after all children.
 
1101
 
 
1102
        :param path1: first path
 
1103
        :param path2: the second path
 
1104
        :return: negative number if ``path1`` comes first,
 
1105
            0 if paths are equal
 
1106
            and a positive number if ``path2`` sorts first
 
1107
        """
 
1108
        # Shortcut this special case
 
1109
        if path1 == path2:
 
1110
            return 0
 
1111
        # This is stolen from _dirstate_helpers_py.py, only switching it to
 
1112
        # Unicode objects. Consider using encode_utf8() and then using the
 
1113
        # optimized versions, or maybe writing optimized unicode versions.
 
1114
        if not isinstance(path1, unicode):
 
1115
            raise TypeError("'path1' must be a unicode string, not %s: %r"
 
1116
                            % (type(path1), path1))
 
1117
        if not isinstance(path2, unicode):
 
1118
            raise TypeError("'path2' must be a unicode string, not %s: %r"
 
1119
                            % (type(path2), path2))
 
1120
        return cmp(MultiWalker._path_to_key(path1),
 
1121
                   MultiWalker._path_to_key(path2))
 
1122
 
 
1123
    @staticmethod
 
1124
    def _path_to_key(path):
 
1125
        dirname, basename = osutils.split(path)
 
1126
        return (dirname.split(u'/'), basename)
 
1127
 
 
1128
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
 
1129
        """Lookup an inventory entry by file_id.
 
1130
 
 
1131
        This is called when an entry is missing in the normal order.
 
1132
        Generally this is because a file was either renamed, or it was
 
1133
        deleted/added. If the entry was found in the inventory and not in
 
1134
        extra_entries, it will be added to self._out_of_order_processed
 
1135
 
 
1136
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
 
1137
            should be filled with entries that were found before they were
 
1138
            used. If file_id is present, it will be removed from the
 
1139
            dictionary.
 
1140
        :param other_tree: The Tree to search, in case we didn't find the entry
 
1141
            yet.
 
1142
        :param file_id: The file_id to look for
 
1143
        :return: (path, ie) if found or (None, None) if not present.
 
1144
        """
 
1145
        if file_id in extra_entries:
 
1146
            return extra_entries.pop(file_id)
 
1147
        # TODO: Is id2path better as the first call, or is
 
1148
        #       inventory[file_id] better as a first check?
 
1149
        try:
 
1150
            cur_path = other_tree.id2path(file_id)
 
1151
        except errors.NoSuchId:
 
1152
            cur_path = None
 
1153
        if cur_path is None:
 
1154
            return (None, None)
 
1155
        else:
 
1156
            self._out_of_order_processed.add(file_id)
 
1157
            cur_ie = other_tree.inventory[file_id]
 
1158
            return (cur_path, cur_ie)
 
1159
 
 
1160
    def iter_all(self):
 
1161
        """Match up the values in the different trees."""
 
1162
        for result in self._walk_master_tree():
 
1163
            yield result
 
1164
        self._finish_others()
 
1165
        for result in self._walk_others():
 
1166
            yield result
 
1167
 
 
1168
    def _walk_master_tree(self):
 
1169
        """First pass, walk all trees in lock-step.
 
1170
        
 
1171
        When we are done, all nodes in the master_tree will have been
 
1172
        processed. _other_walkers, _other_entries, and _others_extra will be
 
1173
        set on 'self' for future processing.
 
1174
        """
 
1175
        # This iterator has the most "inlining" done, because it tends to touch
 
1176
        # every file in the tree, while the others only hit nodes that don't
 
1177
        # match.
 
1178
        master_iterator = self._master_tree.iter_entries_by_dir()
 
1179
 
 
1180
        other_walkers = [other.iter_entries_by_dir()
 
1181
                         for other in self._other_trees]
 
1182
        other_entries = [self._step_one(walker) for walker in other_walkers]
 
1183
        # Track extra nodes in the other trees
 
1184
        others_extra = [{} for i in xrange(len(self._other_trees))]
 
1185
 
 
1186
        master_has_more = True
 
1187
        step_one = self._step_one
 
1188
        lookup_by_file_id = self._lookup_by_file_id
 
1189
        out_of_order_processed = self._out_of_order_processed
 
1190
 
 
1191
        while master_has_more:
 
1192
            (master_has_more, path, master_ie) = step_one(master_iterator)
 
1193
            if not master_has_more:
 
1194
                break
 
1195
 
 
1196
            file_id = master_ie.file_id
 
1197
            other_values = []
 
1198
            other_values_append = other_values.append
 
1199
            next_other_entries = []
 
1200
            next_other_entries_append = next_other_entries.append
 
1201
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
 
1202
                if not other_has_more:
 
1203
                    other_values_append(lookup_by_file_id(
 
1204
                        others_extra[idx], self._other_trees[idx], file_id))
 
1205
                    next_other_entries_append((False, None, None))
 
1206
                elif file_id == other_ie.file_id:
 
1207
                    # This is the critical code path, as most of the entries
 
1208
                    # should match between most trees.
 
1209
                    other_values_append((other_path, other_ie))
 
1210
                    next_other_entries_append(step_one(other_walkers[idx]))
 
1211
                else:
 
1212
                    # This walker did not match, step it until it either
 
1213
                    # matches, or we know we are past the current walker.
 
1214
                    other_walker = other_walkers[idx]
 
1215
                    other_extra = others_extra[idx]
 
1216
                    while (other_has_more and
 
1217
                           self._cmp_path_by_dirblock(other_path, path) < 0):
 
1218
                        other_file_id = other_ie.file_id
 
1219
                        if other_file_id not in out_of_order_processed:
 
1220
                            other_extra[other_file_id] = (other_path, other_ie)
 
1221
                        other_has_more, other_path, other_ie = \
 
1222
                            step_one(other_walker)
 
1223
                    if other_has_more and other_ie.file_id == file_id:
 
1224
                        # We ended up walking to this point, match and step
 
1225
                        # again
 
1226
                        other_values_append((other_path, other_ie))
 
1227
                        other_has_more, other_path, other_ie = \
 
1228
                            step_one(other_walker)
 
1229
                    else:
 
1230
                        # This record isn't in the normal order, see if it
 
1231
                        # exists at all.
 
1232
                        other_values_append(lookup_by_file_id(
 
1233
                            other_extra, self._other_trees[idx], file_id))
 
1234
                    next_other_entries_append((other_has_more, other_path,
 
1235
                                               other_ie))
 
1236
            other_entries = next_other_entries
 
1237
 
 
1238
            # We've matched all the walkers, yield this datapoint
 
1239
            yield path, file_id, master_ie, other_values
 
1240
        self._other_walkers = other_walkers
 
1241
        self._other_entries = other_entries
 
1242
        self._others_extra = others_extra
 
1243
 
 
1244
    def _finish_others(self):
 
1245
        """Finish walking the other iterators, so we get all entries."""
 
1246
        for idx, info in enumerate(self._other_entries):
 
1247
            other_extra = self._others_extra[idx]
 
1248
            (other_has_more, other_path, other_ie) = info
 
1249
            while other_has_more:
 
1250
                other_file_id = other_ie.file_id
 
1251
                if other_file_id not in self._out_of_order_processed:
 
1252
                    other_extra[other_file_id] = (other_path, other_ie)
 
1253
                other_has_more, other_path, other_ie = \
 
1254
                    self._step_one(self._other_walkers[idx])
 
1255
        del self._other_entries
 
1256
 
 
1257
    def _walk_others(self):
 
1258
        """Finish up by walking all the 'deferred' nodes."""
 
1259
        # TODO: One alternative would be to grab all possible unprocessed
 
1260
        #       file_ids, and then sort by path, and then yield them. That
 
1261
        #       might ensure better ordering, in case a caller strictly
 
1262
        #       requires parents before children.
 
1263
        for idx, other_extra in enumerate(self._others_extra):
 
1264
            others = sorted(other_extra.itervalues(),
 
1265
                            key=lambda x: self._path_to_key(x[0]))
 
1266
            for other_path, other_ie in others:
 
1267
                file_id = other_ie.file_id
 
1268
                # We don't need to check out_of_order_processed here, because
 
1269
                # the lookup_by_file_id will be removing anything processed
 
1270
                # from the extras cache
 
1271
                other_extra.pop(file_id)
 
1272
                other_values = [(None, None) for i in xrange(idx)]
 
1273
                other_values.append((other_path, other_ie))
 
1274
                for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
 
1275
                    alt_idx = alt_idx + idx + 1
 
1276
                    alt_extra = self._others_extra[alt_idx]
 
1277
                    alt_tree = self._other_trees[alt_idx]
 
1278
                    other_values.append(self._lookup_by_file_id(
 
1279
                                            alt_extra, alt_tree, file_id))
 
1280
                yield other_path, file_id, None, other_values