~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

  • Committer: Jelmer Vernooij
  • Date: 2012-01-19 00:55:26 UTC
  • mto: (6437.3.23 2.5)
  • mto: This revision was merged to the branch mainline in revision 6451.
  • Revision ID: jelmer@samba.org-20120119005526-q2gst8d3v8qtqpot
Avoid the word safe.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2009 Canonical Ltd
 
1
# Copyright (C) 2005-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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 (
26
29
    conflicts as _mod_conflicts,
27
30
    debug,
28
31
    delta,
 
32
    errors,
29
33
    filters,
 
34
    inventory,
30
35
    osutils,
31
36
    revision as _mod_revision,
32
37
    rules,
33
 
    symbol_versioning,
 
38
    trace,
34
39
    )
 
40
from bzrlib.i18n import gettext
 
41
""")
 
42
 
35
43
from bzrlib.decorators import needs_read_lock
36
 
from bzrlib.errors import BzrError, BzrCheckError, NoSuchId
37
 
from bzrlib import errors
38
 
from bzrlib.inventory import Inventory, InventoryFile
39
44
from bzrlib.inter import InterObject
40
 
from bzrlib.osutils import fingerprint_file
41
 
import bzrlib.revision
42
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
43
 
from bzrlib.trace import mutter, note
 
45
from bzrlib.symbol_versioning import (
 
46
    deprecated_in,
 
47
    deprecated_method,
 
48
    )
44
49
 
45
50
 
46
51
class Tree(object):
52
57
 
53
58
    * `RevisionTree` is a tree as recorded at some point in the past.
54
59
 
55
 
    Trees contain an `Inventory` object, and also know how to retrieve
56
 
    file texts mentioned in the inventory, either from a working
57
 
    directory or from a store.
58
 
 
59
 
    It is possible for trees to contain files that are not described
60
 
    in their inventory or vice versa; for this use `filenames()`.
61
 
 
62
60
    Trees can be compared, etc, regardless of whether they are working
63
61
    trees or versioned trees.
64
62
    """
65
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
 
66
72
    def changes_from(self, other, want_unchanged=False, specific_files=None,
67
73
        extra_trees=None, require_versioned=False, include_root=False,
68
74
        want_unversioned=False):
100
106
    def iter_changes(self, from_tree, include_unchanged=False,
101
107
                     specific_files=None, pb=None, extra_trees=None,
102
108
                     require_versioned=True, want_unversioned=False):
 
109
        """See InterTree.iter_changes"""
103
110
        intertree = InterTree.get(from_tree, self)
104
111
        return intertree.iter_changes(include_unchanged, specific_files, pb,
105
112
            extra_trees, require_versioned, want_unversioned=want_unversioned)
129
136
        raise NotImplementedError(self.has_filename)
130
137
 
131
138
    def has_id(self, file_id):
132
 
        return self.inventory.has_id(file_id)
 
139
        raise NotImplementedError(self.has_id)
133
140
 
 
141
    @deprecated_method(deprecated_in((2, 4, 0)))
134
142
    def __contains__(self, file_id):
135
143
        return self.has_id(file_id)
136
144
 
137
145
    def has_or_had_id(self, file_id):
138
 
        if file_id == self.inventory.root.file_id:
139
 
            return True
140
 
        return self.inventory.has_id(file_id)
 
146
        raise NotImplementedError(self.has_or_had_id)
141
147
 
142
148
    def is_ignored(self, filename):
143
149
        """Check whether the filename is ignored by this tree.
147
153
        """
148
154
        return False
149
155
 
150
 
    def __iter__(self):
151
 
        return iter(self.inventory)
152
 
 
153
156
    def all_file_ids(self):
154
157
        """Iterate through all file ids, including ids for missing files."""
155
 
        return set(self.inventory)
 
158
        raise NotImplementedError(self.all_file_ids)
156
159
 
157
160
    def id2path(self, file_id):
158
161
        """Return the path for a file id.
159
162
 
160
163
        :raises NoSuchId:
161
164
        """
162
 
        return self.inventory.id2path(file_id)
163
 
 
164
 
    def is_control_filename(self, filename):
165
 
        """True if filename is the name of a control file in this tree.
166
 
 
167
 
        :param filename: A filename within the tree. This is a relative path
168
 
        from the root of this tree.
169
 
 
170
 
        This is true IF and ONLY IF the filename is part of the meta data
171
 
        that bzr controls in this tree. I.E. a random .bzr directory placed
172
 
        on disk will not be a control file for this tree.
173
 
        """
174
 
        return self.bzrdir.is_control_filename(filename)
175
 
 
176
 
    @needs_read_lock
177
 
    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):
178
168
        """Walk the tree in 'by_dir' order.
179
169
 
180
170
        This will yield each entry in the tree as a (path, entry) tuple.
196
186
             g
197
187
 
198
188
        The yield order (ignoring root) would be::
 
189
 
199
190
          a, f, a/b, a/d, a/b/c, a/d/e, f/g
200
 
        """
201
 
        return self.inventory.iter_entries_by_dir(
202
 
            specific_file_ids=specific_file_ids)
 
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 list_files(self, include_root=False, from_dir=None, recursive=True):
 
199
        """List all files in this tree.
 
200
 
 
201
        :param include_root: Whether to include the entry for the tree root
 
202
        :param from_dir: Directory under which to list files
 
203
        :param recursive: Whether to list files recursively
 
204
        :return: iterator over tuples of (path, versioned, kind, file_id,
 
205
            inventory entry)
 
206
        """
 
207
        raise NotImplementedError(self.list_files)
203
208
 
204
209
    def iter_references(self):
205
210
        if self.supports_tree_reference():
222
227
    def path_content_summary(self, path):
223
228
        """Get a summary of the information about path.
224
229
 
 
230
        All the attributes returned are for the canonical form, not the
 
231
        convenient form (if content filters are in use.)
 
232
 
225
233
        :param path: A relative path within the tree.
226
234
        :return: A tuple containing kind, size, exec, sha1-or-link.
227
235
            Kind is always present (see tree.kind()).
228
 
            size is present if kind is file, None otherwise.
 
236
            size is present if kind is file and the size of the 
 
237
                canonical form can be cheaply determined, None otherwise.
229
238
            exec is None unless kind is file and the platform supports the 'x'
230
239
                bit.
231
240
            sha1-or-link is the link target if kind is symlink, or the sha1 if
252
261
    def _file_size(self, entry, stat_value):
253
262
        raise NotImplementedError(self._file_size)
254
263
 
255
 
    def _get_inventory(self):
256
 
        return self._inventory
257
 
 
258
264
    def get_file(self, file_id, path=None):
259
265
        """Return a file object for the file file_id in the tree.
260
266
 
282
288
 
283
289
        :param file_id: The file_id of the file.
284
290
        :param path: The path of the file.
 
291
 
285
292
        If both file_id and path are supplied, an implementation may use
286
293
        either one.
 
294
 
 
295
        :returns: A single byte string for the whole file.
287
296
        """
288
297
        my_file = self.get_file(file_id, path)
289
298
        try:
296
305
 
297
306
        :param file_id: The file_id of the file.
298
307
        :param path: The path of the file.
 
308
 
299
309
        If both file_id and path are supplied, an implementation may use
300
310
        either one.
301
311
        """
302
312
        return osutils.split_lines(self.get_file_text(file_id, path))
303
313
 
 
314
    def get_file_verifier(self, file_id, path=None, stat_value=None):
 
315
        """Return a verifier for a file.
 
316
 
 
317
        The default implementation returns a sha1.
 
318
 
 
319
        :param file_id: The handle for this file.
 
320
        :param path: The path that this file can be found at.
 
321
            These must point to the same object.
 
322
        :param stat_value: Optional stat value for the object
 
323
        :return: Tuple with verifier name and verifier data
 
324
        """
 
325
        return ("SHA1", self.get_file_sha1(file_id, path=path,
 
326
            stat_value=stat_value))
 
327
 
 
328
    def get_file_sha1(self, file_id, path=None, stat_value=None):
 
329
        """Return the SHA1 file for a file.
 
330
 
 
331
        :note: callers should use get_file_verifier instead
 
332
            where possible, as the underlying repository implementation may
 
333
            have quicker access to a non-sha1 verifier.
 
334
 
 
335
        :param file_id: The handle for this file.
 
336
        :param path: The path that this file can be found at.
 
337
            These must point to the same object.
 
338
        :param stat_value: Optional stat value for the object
 
339
        """
 
340
        raise NotImplementedError(self.get_file_sha1)
 
341
 
304
342
    def get_file_mtime(self, file_id, path=None):
305
343
        """Return the modification time for a file.
306
344
 
319
357
        """
320
358
        raise NotImplementedError(self.get_file_size)
321
359
 
322
 
    def get_file_by_path(self, path):
323
 
        return self.get_file(self._inventory.path2id(path), path)
 
360
    def is_executable(self, file_id, path=None):
 
361
        """Check if a file is executable.
 
362
 
 
363
        :param file_id: The handle for this file.
 
364
        :param path: The path that this file can be found at.
 
365
            These must point to the same object.
 
366
        """
 
367
        raise NotImplementedError(self.is_executable)
324
368
 
325
369
    def iter_files_bytes(self, desired_files):
326
370
        """Iterate through file contents.
348
392
            cur_file = (self.get_file_text(file_id),)
349
393
            yield identifier, cur_file
350
394
 
351
 
    def get_symlink_target(self, file_id):
 
395
    def get_symlink_target(self, file_id, path=None):
352
396
        """Get the target for a given file_id.
353
397
 
354
398
        It is assumed that the caller already knows that file_id is referencing
355
399
        a symlink.
356
400
        :param file_id: Handle for the symlink entry.
 
401
        :param path: The path of the file.
 
402
        If both file_id and path are supplied, an implementation may use
 
403
        either one.
357
404
        :return: The path the symlink points to.
358
405
        """
359
406
        raise NotImplementedError(self.get_symlink_target)
360
407
 
361
 
    def get_canonical_inventory_paths(self, paths):
362
 
        """Like get_canonical_inventory_path() but works on multiple items.
363
 
 
364
 
        :param paths: A sequence of paths relative to the root of the tree.
365
 
        :return: A list of paths, with each item the corresponding input path
366
 
        adjusted to account for existing elements that match case
367
 
        insensitively.
368
 
        """
369
 
        return list(self._yield_canonical_inventory_paths(paths))
370
 
 
371
 
    def get_canonical_inventory_path(self, path):
372
 
        """Returns the first inventory item that case-insensitively matches path.
373
 
 
374
 
        If a path matches exactly, it is returned. If no path matches exactly
375
 
        but more than one path matches case-insensitively, it is implementation
376
 
        defined which is returned.
377
 
 
378
 
        If no path matches case-insensitively, the input path is returned, but
379
 
        with as many path entries that do exist changed to their canonical
380
 
        form.
381
 
 
382
 
        If you need to resolve many names from the same tree, you should
383
 
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
384
 
 
385
 
        :param path: A paths relative to the root of the tree.
386
 
        :return: The input path adjusted to account for existing elements
387
 
        that match case insensitively.
388
 
        """
389
 
        return self._yield_canonical_inventory_paths([path]).next()
390
 
 
391
 
    def _yield_canonical_inventory_paths(self, paths):
392
 
        for path in paths:
393
 
            # First, if the path as specified exists exactly, just use it.
394
 
            if self.path2id(path) is not None:
395
 
                yield path
396
 
                continue
397
 
            # go walkin...
398
 
            cur_id = self.get_root_id()
399
 
            cur_path = ''
400
 
            bit_iter = iter(path.split("/"))
401
 
            for elt in bit_iter:
402
 
                lelt = elt.lower()
403
 
                for child in self.iter_children(cur_id):
404
 
                    try:
405
 
                        child_base = os.path.basename(self.id2path(child))
406
 
                        if child_base.lower() == lelt:
407
 
                            cur_id = child
408
 
                            cur_path = osutils.pathjoin(cur_path, child_base)
409
 
                            break
410
 
                    except NoSuchId:
411
 
                        # before a change is committed we can see this error...
412
 
                        continue
413
 
                else:
414
 
                    # got to the end of this directory and no entries matched.
415
 
                    # Return what matched so far, plus the rest as specified.
416
 
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
417
 
                    break
418
 
            yield cur_path
419
 
        # all done.
420
 
 
421
408
    def get_root_id(self):
422
409
        """Return the file_id for the root of this tree."""
423
410
        raise NotImplementedError(self.get_root_id)
437
424
        raise NotImplementedError(self.annotate_iter)
438
425
 
439
426
    def _get_plan_merge_data(self, file_id, other, base):
440
 
        from bzrlib import merge, versionedfile
 
427
        from bzrlib import versionedfile
441
428
        vf = versionedfile._PlanMergeVersionedFile(file_id)
442
429
        last_revision_a = self._get_file_revision(file_id, vf, 'this:')
443
430
        last_revision_b = other._get_file_revision(file_id, vf, 'other:')
481
468
            except errors.NoSuchRevisionInTree:
482
469
                yield self.repository.revision_tree(revision_id)
483
470
 
484
 
    @staticmethod
485
 
    def _file_revision(revision_tree, file_id):
486
 
        """Determine the revision associated with a file in a given tree."""
487
 
        revision_tree.lock_read()
488
 
        try:
489
 
            return revision_tree.inventory[file_id].revision
490
 
        finally:
491
 
            revision_tree.unlock()
492
 
 
493
471
    def _get_file_revision(self, file_id, vf, tree_revision):
494
472
        """Ensure that file_id, tree_revision is in vf to plan the merge."""
495
473
 
496
474
        if getattr(self, '_repository', None) is None:
497
475
            last_revision = tree_revision
498
 
            parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
 
476
            parent_keys = [(file_id, t.get_file_revision(file_id)) for t in
499
477
                self._iter_parent_trees()]
500
478
            vf.add_lines((file_id, last_revision), parent_keys,
501
 
                         self.get_file(file_id).readlines())
 
479
                         self.get_file_lines(file_id))
502
480
            repo = self.branch.repository
503
481
            base_vf = repo.texts
504
482
        else:
505
 
            last_revision = self._file_revision(self, file_id)
 
483
            last_revision = self.get_file_revision(file_id)
506
484
            base_vf = self._repository.texts
507
485
        if base_vf not in vf.fallback_versionedfiles:
508
486
            vf.fallback_versionedfiles.append(base_vf)
509
487
        return last_revision
510
488
 
511
 
    inventory = property(_get_inventory,
512
 
                         doc="Inventory of this Tree")
513
 
 
514
489
    def _check_retrieved(self, ie, f):
515
490
        if not __debug__:
516
491
            return
517
 
        fp = fingerprint_file(f)
 
492
        fp = osutils.fingerprint_file(f)
518
493
        f.seek(0)
519
494
 
520
495
        if ie.text_size is not None:
521
496
            if ie.text_size != fp['size']:
522
 
                raise BzrError("mismatched size for file %r in %r" % (ie.file_id, self._store),
 
497
                raise errors.BzrError(
 
498
                        "mismatched size for file %r in %r" %
 
499
                        (ie.file_id, self._store),
523
500
                        ["inventory expects %d bytes" % ie.text_size,
524
501
                         "file is actually %d bytes" % fp['size'],
525
502
                         "store is probably damaged/corrupt"])
526
503
 
527
504
        if ie.text_sha1 != fp['sha1']:
528
 
            raise BzrError("wrong SHA-1 for file %r in %r" % (ie.file_id, self._store),
 
505
            raise errors.BzrError("wrong SHA-1 for file %r in %r" %
 
506
                    (ie.file_id, self._store),
529
507
                    ["inventory expects %s" % ie.text_sha1,
530
508
                     "file is actually %s" % fp['sha1'],
531
509
                     "store is probably damaged/corrupt"])
532
510
 
533
 
    @needs_read_lock
534
511
    def path2id(self, path):
535
512
        """Return the id for path in this tree."""
536
 
        return self._inventory.path2id(path)
 
513
        raise NotImplementedError(self.path2id)
537
514
 
538
515
    def paths2ids(self, paths, trees=[], require_versioned=True):
539
516
        """Return all the ids that can be reached by walking from paths.
560
537
            yield child.file_id
561
538
 
562
539
    def lock_read(self):
 
540
        """Lock this tree for multiple read only operations.
 
541
        
 
542
        :return: A bzrlib.lock.LogicalLockResult.
 
543
        """
563
544
        pass
564
545
 
565
546
    def revision_tree(self, revision_id):
592
573
 
593
574
        :return: set of paths.
594
575
        """
595
 
        # NB: we specifically *don't* call self.has_filename, because for
596
 
        # WorkingTrees that can indicate files that exist on disk but that
597
 
        # are not versioned.
598
 
        pred = self.inventory.has_filename
599
 
        return set((p for p in paths if not pred(p)))
 
576
        raise NotImplementedError(self.filter_unversioned_files)
600
577
 
601
578
    def walkdirs(self, prefix=""):
602
579
        """Walk the contents of this tree from path down.
654
631
        prefs = self.iter_search_rules([path], filter_pref_names).next()
655
632
        stk = filters._get_filter_stack_for(prefs)
656
633
        if 'filters' in debug.debug_flags:
657
 
            note("*** %s content-filter: %s => %r" % (path,prefs,stk))
 
634
            trace.note(gettext("*** {0} content-filter: {1} => {2!r}").format(path,prefs,stk))
658
635
        return stk
659
636
 
660
637
    def _content_filter_stack_provider(self):
693
670
                for path in path_names:
694
671
                    yield searcher.get_items(path)
695
672
 
696
 
    @needs_read_lock
697
673
    def _get_rules_searcher(self, default_searcher):
698
674
        """Get the RulesSearcher for this tree given the default one."""
699
675
        searcher = default_searcher
700
676
        return searcher
701
677
 
702
678
 
703
 
######################################################################
704
 
# diff
705
 
 
706
 
# TODO: Merge these two functions into a single one that can operate
707
 
# on either a whole tree or a set of files.
708
 
 
709
 
# TODO: Return the diff in order by filename, not by category or in
710
 
# random order.  Can probably be done by lock-stepping through the
711
 
# filenames from both trees.
712
 
 
713
 
 
714
 
def file_status(filename, old_tree, new_tree):
715
 
    """Return single-letter status, old and new names for a file.
716
 
 
717
 
    The complexity here is in deciding how to represent renames;
718
 
    many complex cases are possible.
 
679
class InventoryTree(Tree):
 
680
    """A tree that relies on an inventory for its metadata.
 
681
 
 
682
    Trees contain an `Inventory` object, and also know how to retrieve
 
683
    file texts mentioned in the inventory, either from a working
 
684
    directory or from a store.
 
685
 
 
686
    It is possible for trees to contain files that are not described
 
687
    in their inventory or vice versa; for this use `filenames()`.
 
688
 
 
689
    Subclasses should set the _inventory attribute, which is considered
 
690
    private to external API users.
719
691
    """
720
 
    old_inv = old_tree.inventory
721
 
    new_inv = new_tree.inventory
722
 
    new_id = new_inv.path2id(filename)
723
 
    old_id = old_inv.path2id(filename)
724
 
 
725
 
    if not new_id and not old_id:
726
 
        # easy: doesn't exist in either; not versioned at all
727
 
        if new_tree.is_ignored(filename):
728
 
            return 'I', None, None
729
 
        else:
730
 
            return '?', None, None
731
 
    elif new_id:
732
 
        # There is now a file of this name, great.
733
 
        pass
734
 
    else:
735
 
        # There is no longer a file of this name, but we can describe
736
 
        # what happened to the file that used to have
737
 
        # this name.  There are two possibilities: either it was
738
 
        # deleted entirely, or renamed.
739
 
        if new_inv.has_id(old_id):
740
 
            return 'X', old_inv.id2path(old_id), new_inv.id2path(old_id)
741
 
        else:
742
 
            return 'D', old_inv.id2path(old_id), None
743
 
 
744
 
    # if the file_id is new in this revision, it is added
745
 
    if new_id and not old_inv.has_id(new_id):
746
 
        return 'A'
747
 
 
748
 
    # if there used to be a file of this name, but that ID has now
749
 
    # disappeared, it is deleted
750
 
    if old_id and not new_inv.has_id(old_id):
751
 
        return 'D'
752
 
 
753
 
    return 'wtf?'
754
 
 
755
 
 
756
 
@deprecated_function(deprecated_in((1, 9, 0)))
757
 
def find_renames(old_inv, new_inv):
758
 
    for file_id in old_inv:
759
 
        if file_id not in new_inv:
760
 
            continue
761
 
        old_name = old_inv.id2path(file_id)
762
 
        new_name = new_inv.id2path(file_id)
763
 
        if old_name != new_name:
764
 
            yield (old_name, new_name)
 
692
 
 
693
    def get_canonical_inventory_paths(self, paths):
 
694
        """Like get_canonical_inventory_path() but works on multiple items.
 
695
 
 
696
        :param paths: A sequence of paths relative to the root of the tree.
 
697
        :return: A list of paths, with each item the corresponding input path
 
698
        adjusted to account for existing elements that match case
 
699
        insensitively.
 
700
        """
 
701
        return list(self._yield_canonical_inventory_paths(paths))
 
702
 
 
703
    def get_canonical_inventory_path(self, path):
 
704
        """Returns the first inventory item that case-insensitively matches path.
 
705
 
 
706
        If a path matches exactly, it is returned. If no path matches exactly
 
707
        but more than one path matches case-insensitively, it is implementation
 
708
        defined which is returned.
 
709
 
 
710
        If no path matches case-insensitively, the input path is returned, but
 
711
        with as many path entries that do exist changed to their canonical
 
712
        form.
 
713
 
 
714
        If you need to resolve many names from the same tree, you should
 
715
        use get_canonical_inventory_paths() to avoid O(N) behaviour.
 
716
 
 
717
        :param path: A paths relative to the root of the tree.
 
718
        :return: The input path adjusted to account for existing elements
 
719
        that match case insensitively.
 
720
        """
 
721
        return self._yield_canonical_inventory_paths([path]).next()
 
722
 
 
723
    def _yield_canonical_inventory_paths(self, paths):
 
724
        for path in paths:
 
725
            # First, if the path as specified exists exactly, just use it.
 
726
            if self.path2id(path) is not None:
 
727
                yield path
 
728
                continue
 
729
            # go walkin...
 
730
            cur_id = self.get_root_id()
 
731
            cur_path = ''
 
732
            bit_iter = iter(path.split("/"))
 
733
            for elt in bit_iter:
 
734
                lelt = elt.lower()
 
735
                new_path = None
 
736
                for child in self.iter_children(cur_id):
 
737
                    try:
 
738
                        # XXX: it seem like if the child is known to be in the
 
739
                        # tree, we shouldn't need to go from its id back to
 
740
                        # its path -- mbp 2010-02-11
 
741
                        #
 
742
                        # XXX: it seems like we could be more efficient
 
743
                        # by just directly looking up the original name and
 
744
                        # only then searching all children; also by not
 
745
                        # chopping paths so much. -- mbp 2010-02-11
 
746
                        child_base = os.path.basename(self.id2path(child))
 
747
                        if (child_base == elt):
 
748
                            # if we found an exact match, we can stop now; if
 
749
                            # we found an approximate match we need to keep
 
750
                            # searching because there might be an exact match
 
751
                            # later.  
 
752
                            cur_id = child
 
753
                            new_path = osutils.pathjoin(cur_path, child_base)
 
754
                            break
 
755
                        elif child_base.lower() == lelt:
 
756
                            cur_id = child
 
757
                            new_path = osutils.pathjoin(cur_path, child_base)
 
758
                    except errors.NoSuchId:
 
759
                        # before a change is committed we can see this error...
 
760
                        continue
 
761
                if new_path:
 
762
                    cur_path = new_path
 
763
                else:
 
764
                    # got to the end of this directory and no entries matched.
 
765
                    # Return what matched so far, plus the rest as specified.
 
766
                    cur_path = osutils.pathjoin(cur_path, elt, *list(bit_iter))
 
767
                    break
 
768
            yield cur_path
 
769
        # all done.
 
770
 
 
771
    def _get_inventory(self):
 
772
        return self._inventory
 
773
 
 
774
    inventory = property(_get_inventory,
 
775
                         doc="Inventory of this Tree")
 
776
 
 
777
    @needs_read_lock
 
778
    def path2id(self, path):
 
779
        """Return the id for path in this tree."""
 
780
        return self._inventory.path2id(path)
 
781
 
 
782
    def id2path(self, file_id):
 
783
        """Return the path for a file id.
 
784
 
 
785
        :raises NoSuchId:
 
786
        """
 
787
        return self.inventory.id2path(file_id)
 
788
 
 
789
    def has_id(self, file_id):
 
790
        return self.inventory.has_id(file_id)
 
791
 
 
792
    def has_or_had_id(self, file_id):
 
793
        return self.inventory.has_id(file_id)
 
794
 
 
795
    def all_file_ids(self):
 
796
        return set(self.inventory)
 
797
 
 
798
    @deprecated_method(deprecated_in((2, 4, 0)))
 
799
    def __iter__(self):
 
800
        return iter(self.inventory)
 
801
 
 
802
    def filter_unversioned_files(self, paths):
 
803
        """Filter out paths that are versioned.
 
804
 
 
805
        :return: set of paths.
 
806
        """
 
807
        # NB: we specifically *don't* call self.has_filename, because for
 
808
        # WorkingTrees that can indicate files that exist on disk but that
 
809
        # are not versioned.
 
810
        pred = self.inventory.has_filename
 
811
        return set((p for p in paths if not pred(p)))
 
812
 
 
813
    @needs_read_lock
 
814
    def iter_entries_by_dir(self, specific_file_ids=None, yield_parents=False):
 
815
        """Walk the tree in 'by_dir' order.
 
816
 
 
817
        This will yield each entry in the tree as a (path, entry) tuple.
 
818
        The order that they are yielded is:
 
819
 
 
820
        See Tree.iter_entries_by_dir for details.
 
821
 
 
822
        :param yield_parents: If True, yield the parents from the root leading
 
823
            down to specific_file_ids that have been requested. This has no
 
824
            impact if specific_file_ids is None.
 
825
        """
 
826
        return self.inventory.iter_entries_by_dir(
 
827
            specific_file_ids=specific_file_ids, yield_parents=yield_parents)
 
828
 
 
829
    @deprecated_method(deprecated_in((2, 5, 0)))
 
830
    def get_file_by_path(self, path):
 
831
        return self.get_file(self.path2id(path), path)
765
832
 
766
833
 
767
834
def find_ids_across_trees(filenames, trees, require_versioned=True):
774
841
        None)
775
842
    :param trees: The trees to find file_ids within
776
843
    :param require_versioned: if true, all specified filenames must occur in
777
 
    at least one tree.
 
844
        at least one tree.
778
845
    :return: a set of file ids for the specified filenames and their children.
779
846
    """
780
847
    if not filenames:
827
894
        new_pending = set()
828
895
        for file_id in pending:
829
896
            for tree in trees:
830
 
                if not tree.has_id(file_id):
 
897
                if not tree.has_or_had_id(file_id):
831
898
                    continue
832
899
                for child_id in tree.iter_children(file_id):
833
900
                    if child_id not in interesting_ids:
848
915
    will pass through to InterTree as appropriate.
849
916
    """
850
917
 
 
918
    # Formats that will be used to test this InterTree. If both are
 
919
    # None, this InterTree will not be tested (e.g. because a complex
 
920
    # setup is required)
 
921
    _matching_from_tree_format = None
 
922
    _matching_to_tree_format = None
 
923
 
851
924
    _optimisers = []
852
925
 
 
926
    @classmethod
 
927
    def is_compatible(kls, source, target):
 
928
        # The default implementation is naive and uses the public API, so
 
929
        # it works for all trees.
 
930
        return True
 
931
 
 
932
    def _changes_from_entries(self, source_entry, target_entry,
 
933
        source_path=None, target_path=None):
 
934
        """Generate a iter_changes tuple between source_entry and target_entry.
 
935
 
 
936
        :param source_entry: An inventory entry from self.source, or None.
 
937
        :param target_entry: An inventory entry from self.target, or None.
 
938
        :param source_path: The path of source_entry, if known. If not known
 
939
            it will be looked up.
 
940
        :param target_path: The path of target_entry, if known. If not known
 
941
            it will be looked up.
 
942
        :return: A tuple, item 0 of which is an iter_changes result tuple, and
 
943
            item 1 is True if there are any changes in the result tuple.
 
944
        """
 
945
        if source_entry is None:
 
946
            if target_entry is None:
 
947
                return None
 
948
            file_id = target_entry.file_id
 
949
        else:
 
950
            file_id = source_entry.file_id
 
951
        if source_entry is not None:
 
952
            source_versioned = True
 
953
            source_name = source_entry.name
 
954
            source_parent = source_entry.parent_id
 
955
            if source_path is None:
 
956
                source_path = self.source.id2path(file_id)
 
957
            source_kind, source_executable, source_stat = \
 
958
                self.source._comparison_data(source_entry, source_path)
 
959
        else:
 
960
            source_versioned = False
 
961
            source_name = None
 
962
            source_parent = None
 
963
            source_kind = None
 
964
            source_executable = None
 
965
        if target_entry is not None:
 
966
            target_versioned = True
 
967
            target_name = target_entry.name
 
968
            target_parent = target_entry.parent_id
 
969
            if target_path is None:
 
970
                target_path = self.target.id2path(file_id)
 
971
            target_kind, target_executable, target_stat = \
 
972
                self.target._comparison_data(target_entry, target_path)
 
973
        else:
 
974
            target_versioned = False
 
975
            target_name = None
 
976
            target_parent = None
 
977
            target_kind = None
 
978
            target_executable = None
 
979
        versioned = (source_versioned, target_versioned)
 
980
        kind = (source_kind, target_kind)
 
981
        changed_content = False
 
982
        if source_kind != target_kind:
 
983
            changed_content = True
 
984
        elif source_kind == 'file':
 
985
            if not self.file_content_matches(file_id, file_id, source_path,
 
986
                    target_path, source_stat, target_stat):
 
987
                changed_content = True
 
988
        elif source_kind == 'symlink':
 
989
            if (self.source.get_symlink_target(file_id) !=
 
990
                self.target.get_symlink_target(file_id)):
 
991
                changed_content = True
 
992
            # XXX: Yes, the indentation below is wrong. But fixing it broke
 
993
            # test_merge.TestMergerEntriesLCAOnDisk.
 
994
            # test_nested_tree_subtree_renamed_and_modified. We'll wait for
 
995
            # the fix from bzr.dev -- vila 2009026
 
996
            elif source_kind == 'tree-reference':
 
997
                if (self.source.get_reference_revision(file_id, source_path)
 
998
                    != self.target.get_reference_revision(file_id, target_path)):
 
999
                    changed_content = True
 
1000
        parent = (source_parent, target_parent)
 
1001
        name = (source_name, target_name)
 
1002
        executable = (source_executable, target_executable)
 
1003
        if (changed_content is not False or versioned[0] != versioned[1]
 
1004
            or parent[0] != parent[1] or name[0] != name[1] or
 
1005
            executable[0] != executable[1]):
 
1006
            changes = True
 
1007
        else:
 
1008
            changes = False
 
1009
        return (file_id, (source_path, target_path), changed_content,
 
1010
                versioned, parent, name, kind, executable), changes
 
1011
 
853
1012
    @needs_read_lock
854
1013
    def compare(self, want_unchanged=False, specific_files=None,
855
1014
        extra_trees=None, require_versioned=False, include_root=False,
870
1029
            a PathsNotVersionedError will be thrown.
871
1030
        :param want_unversioned: Scan for unversioned paths.
872
1031
        """
873
 
        # NB: show_status depends on being able to pass in non-versioned files
874
 
        # and report them as unknown
875
1032
        trees = (self.source,)
876
1033
        if extra_trees is not None:
877
1034
            trees = trees + tuple(extra_trees)
882
1039
            # All files are unversioned, so just return an empty delta
883
1040
            # _compare_trees would think we want a complete delta
884
1041
            result = delta.TreeDelta()
885
 
            fake_entry = InventoryFile('unused', 'unused', 'unused')
 
1042
            fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
886
1043
            result.unversioned = [(path, None,
887
1044
                self.target._comparison_data(fake_entry, path)[0]) for path in
888
1045
                specific_files]
918
1075
        :param require_versioned: Raise errors.PathsNotVersionedError if a
919
1076
            path in the specific_files list is not versioned in one of
920
1077
            source, target or extra_trees.
 
1078
        :param specific_files: An optional list of file paths to restrict the
 
1079
            comparison to. When mapping filenames to ids, all matches in all
 
1080
            trees (including optional extra_trees) are used, and all children
 
1081
            of matched directories are included. The parents in the target tree
 
1082
            of the specific files up to and including the root of the tree are
 
1083
            always evaluated for changes too.
921
1084
        :param want_unversioned: Should unversioned files be returned in the
922
1085
            output. An unversioned file is defined as one with (False, False)
923
1086
            for the versioned pair.
925
1088
        lookup_trees = [self.source]
926
1089
        if extra_trees:
927
1090
             lookup_trees.extend(extra_trees)
 
1091
        # The ids of items we need to examine to insure delta consistency.
 
1092
        precise_file_ids = set()
 
1093
        changed_file_ids = []
928
1094
        if specific_files == []:
929
1095
            specific_file_ids = []
930
1096
        else:
931
1097
            specific_file_ids = self.target.paths2ids(specific_files,
932
1098
                lookup_trees, require_versioned=require_versioned)
 
1099
        if specific_files is not None:
 
1100
            # reparented or added entries must have their parents included
 
1101
            # so that valid deltas can be created. The seen_parents set
 
1102
            # tracks the parents that we need to have.
 
1103
            # The seen_dirs set tracks directory entries we've yielded.
 
1104
            # After outputting version object in to_entries we set difference
 
1105
            # the two seen sets and start checking parents.
 
1106
            seen_parents = set()
 
1107
            seen_dirs = set()
933
1108
        if want_unversioned:
934
1109
            all_unversioned = sorted([(p.split('/'), p) for p in
935
1110
                                     self.target.extras()
936
1111
                if specific_files is None or
937
1112
                    osutils.is_inside_any(specific_files, p)])
938
 
            all_unversioned = deque(all_unversioned)
 
1113
            all_unversioned = collections.deque(all_unversioned)
939
1114
        else:
940
 
            all_unversioned = deque()
 
1115
            all_unversioned = collections.deque()
941
1116
        to_paths = {}
942
1117
        from_entries_by_dir = list(self.source.iter_entries_by_dir(
943
1118
            specific_file_ids=specific_file_ids))
949
1124
        # the unversioned path lookup only occurs on real trees - where there
950
1125
        # can be extras. So the fake_entry is solely used to look up
951
1126
        # executable it values when execute is not supported.
952
 
        fake_entry = InventoryFile('unused', 'unused', 'unused')
953
 
        for to_path, to_entry in to_entries_by_dir:
954
 
            while all_unversioned and all_unversioned[0][0] < to_path.split('/'):
 
1127
        fake_entry = inventory.InventoryFile('unused', 'unused', 'unused')
 
1128
        for target_path, target_entry in to_entries_by_dir:
 
1129
            while (all_unversioned and
 
1130
                all_unversioned[0][0] < target_path.split('/')):
955
1131
                unversioned_path = all_unversioned.popleft()
956
 
                to_kind, to_executable, to_stat = \
 
1132
                target_kind, target_executable, target_stat = \
957
1133
                    self.target._comparison_data(fake_entry, unversioned_path[1])
958
1134
                yield (None, (None, unversioned_path[1]), True, (False, False),
959
1135
                    (None, None),
960
1136
                    (None, unversioned_path[0][-1]),
961
 
                    (None, to_kind),
962
 
                    (None, to_executable))
963
 
            file_id = to_entry.file_id
964
 
            to_paths[file_id] = to_path
 
1137
                    (None, target_kind),
 
1138
                    (None, target_executable))
 
1139
            source_path, source_entry = from_data.get(target_entry.file_id,
 
1140
                (None, None))
 
1141
            result, changes = self._changes_from_entries(source_entry,
 
1142
                target_entry, source_path=source_path, target_path=target_path)
 
1143
            to_paths[result[0]] = result[1][1]
965
1144
            entry_count += 1
966
 
            changed_content = False
967
 
            from_path, from_entry = from_data.get(file_id, (None, None))
968
 
            from_versioned = (from_entry is not None)
969
 
            if from_entry is not None:
970
 
                from_versioned = True
971
 
                from_name = from_entry.name
972
 
                from_parent = from_entry.parent_id
973
 
                from_kind, from_executable, from_stat = \
974
 
                    self.source._comparison_data(from_entry, from_path)
 
1145
            if result[3][0]:
975
1146
                entry_count += 1
976
 
            else:
977
 
                from_versioned = False
978
 
                from_kind = None
979
 
                from_parent = None
980
 
                from_name = None
981
 
                from_executable = None
982
 
            versioned = (from_versioned, True)
983
 
            to_kind, to_executable, to_stat = \
984
 
                self.target._comparison_data(to_entry, to_path)
985
 
            kind = (from_kind, to_kind)
986
 
            if kind[0] != kind[1]:
987
 
                changed_content = True
988
 
            elif from_kind == 'file':
989
 
                if (self.source.get_file_sha1(file_id, from_path, from_stat) !=
990
 
                    self.target.get_file_sha1(file_id, to_path, to_stat)):
991
 
                    changed_content = True
992
 
            elif from_kind == 'symlink':
993
 
                if (self.source.get_symlink_target(file_id) !=
994
 
                    self.target.get_symlink_target(file_id)):
995
 
                    changed_content = True
996
 
                # XXX: Yes, the indentation below is wrong. But fixing it broke
997
 
                # test_merge.TestMergerEntriesLCAOnDisk.
998
 
                # test_nested_tree_subtree_renamed_and_modified. We'll wait for
999
 
                # the fix from bzr.dev -- vila 2009026
1000
 
                elif from_kind == 'tree-reference':
1001
 
                    if (self.source.get_reference_revision(file_id, from_path)
1002
 
                        != self.target.get_reference_revision(file_id, to_path)):
1003
 
                        changed_content = True
1004
 
            parent = (from_parent, to_entry.parent_id)
1005
 
            name = (from_name, to_entry.name)
1006
 
            executable = (from_executable, to_executable)
1007
1147
            if pb is not None:
1008
1148
                pb.update('comparing files', entry_count, num_entries)
1009
 
            if (changed_content is not False or versioned[0] != versioned[1]
1010
 
                or parent[0] != parent[1] or name[0] != name[1] or
1011
 
                executable[0] != executable[1] or include_unchanged):
1012
 
                yield (file_id, (from_path, to_path), changed_content,
1013
 
                    versioned, parent, name, kind, executable)
1014
 
 
 
1149
            if changes or include_unchanged:
 
1150
                if specific_file_ids is not None:
 
1151
                    new_parent_id = result[4][1]
 
1152
                    precise_file_ids.add(new_parent_id)
 
1153
                    changed_file_ids.append(result[0])
 
1154
                yield result
 
1155
            # Ensure correct behaviour for reparented/added specific files.
 
1156
            if specific_files is not None:
 
1157
                # Record output dirs
 
1158
                if result[6][1] == 'directory':
 
1159
                    seen_dirs.add(result[0])
 
1160
                # Record parents of reparented/added entries.
 
1161
                versioned = result[3]
 
1162
                parents = result[4]
 
1163
                if not versioned[0] or parents[0] != parents[1]:
 
1164
                    seen_parents.add(parents[1])
1015
1165
        while all_unversioned:
1016
1166
            # yield any trailing unversioned paths
1017
1167
            unversioned_path = all_unversioned.popleft()
1022
1172
                (None, unversioned_path[0][-1]),
1023
1173
                (None, to_kind),
1024
1174
                (None, to_executable))
1025
 
 
1026
 
        def get_to_path(to_entry):
1027
 
            if to_entry.parent_id is None:
1028
 
                to_path = '' # the root
1029
 
            else:
1030
 
                if to_entry.parent_id not in to_paths:
1031
 
                    # recurse up
1032
 
                    return get_to_path(self.target.inventory[to_entry.parent_id])
1033
 
                to_path = osutils.pathjoin(to_paths[to_entry.parent_id],
1034
 
                                           to_entry.name)
1035
 
            to_paths[to_entry.file_id] = to_path
1036
 
            return to_path
1037
 
 
 
1175
        # Yield all remaining source paths
1038
1176
        for path, from_entry in from_entries_by_dir:
1039
1177
            file_id = from_entry.file_id
1040
1178
            if file_id in to_paths:
1041
1179
                # already returned
1042
1180
                continue
1043
 
            if not file_id in self.target.all_file_ids():
 
1181
            if not self.target.has_id(file_id):
1044
1182
                # common case - paths we have not emitted are not present in
1045
1183
                # target.
1046
1184
                to_path = None
1047
1185
            else:
1048
 
                to_path = get_to_path(self.target.inventory[file_id])
 
1186
                to_path = self.target.id2path(file_id)
1049
1187
            entry_count += 1
1050
1188
            if pb is not None:
1051
1189
                pb.update('comparing files', entry_count, num_entries)
1058
1196
            executable = (from_executable, None)
1059
1197
            changed_content = from_kind is not None
1060
1198
            # the parent's path is necessarily known at this point.
 
1199
            changed_file_ids.append(file_id)
1061
1200
            yield(file_id, (path, to_path), changed_content, versioned, parent,
1062
1201
                  name, kind, executable)
 
1202
        changed_file_ids = set(changed_file_ids)
 
1203
        if specific_file_ids is not None:
 
1204
            for result in self._handle_precise_ids(precise_file_ids,
 
1205
                changed_file_ids):
 
1206
                yield result
 
1207
 
 
1208
    def _get_entry(self, tree, file_id):
 
1209
        """Get an inventory entry from a tree, with missing entries as None.
 
1210
 
 
1211
        If the tree raises NotImplementedError on accessing .inventory, then
 
1212
        this is worked around using iter_entries_by_dir on just the file id
 
1213
        desired.
 
1214
 
 
1215
        :param tree: The tree to lookup the entry in.
 
1216
        :param file_id: The file_id to lookup.
 
1217
        """
 
1218
        try:
 
1219
            inventory = tree.inventory
 
1220
        except NotImplementedError:
 
1221
            # No inventory available.
 
1222
            try:
 
1223
                iterator = tree.iter_entries_by_dir(specific_file_ids=[file_id])
 
1224
                return iterator.next()[1]
 
1225
            except StopIteration:
 
1226
                return None
 
1227
        else:
 
1228
            try:
 
1229
                return inventory[file_id]
 
1230
            except errors.NoSuchId:
 
1231
                return None
 
1232
 
 
1233
    def _handle_precise_ids(self, precise_file_ids, changed_file_ids,
 
1234
        discarded_changes=None):
 
1235
        """Fill out a partial iter_changes to be consistent.
 
1236
 
 
1237
        :param precise_file_ids: The file ids of parents that were seen during
 
1238
            the iter_changes.
 
1239
        :param changed_file_ids: The file ids of already emitted items.
 
1240
        :param discarded_changes: An optional dict of precalculated
 
1241
            iter_changes items which the partial iter_changes had not output
 
1242
            but had calculated.
 
1243
        :return: A generator of iter_changes items to output.
 
1244
        """
 
1245
        # process parents of things that had changed under the users
 
1246
        # requested paths to prevent incorrect paths or parent ids which
 
1247
        # aren't in the tree.
 
1248
        while precise_file_ids:
 
1249
            precise_file_ids.discard(None)
 
1250
            # Don't emit file_ids twice
 
1251
            precise_file_ids.difference_update(changed_file_ids)
 
1252
            if not precise_file_ids:
 
1253
                break
 
1254
            # If the there was something at a given output path in source, we
 
1255
            # have to include the entry from source in the delta, or we would
 
1256
            # be putting this entry into a used path.
 
1257
            paths = []
 
1258
            for parent_id in precise_file_ids:
 
1259
                try:
 
1260
                    paths.append(self.target.id2path(parent_id))
 
1261
                except errors.NoSuchId:
 
1262
                    # This id has been dragged in from the source by delta
 
1263
                    # expansion and isn't present in target at all: we don't
 
1264
                    # need to check for path collisions on it.
 
1265
                    pass
 
1266
            for path in paths:
 
1267
                old_id = self.source.path2id(path)
 
1268
                precise_file_ids.add(old_id)
 
1269
            precise_file_ids.discard(None)
 
1270
            current_ids = precise_file_ids
 
1271
            precise_file_ids = set()
 
1272
            # We have to emit all of precise_file_ids that have been altered.
 
1273
            # We may have to output the children of some of those ids if any
 
1274
            # directories have stopped being directories.
 
1275
            for file_id in current_ids:
 
1276
                # Examine file_id
 
1277
                if discarded_changes:
 
1278
                    result = discarded_changes.get(file_id)
 
1279
                    old_entry = None
 
1280
                else:
 
1281
                    result = None
 
1282
                if result is None:
 
1283
                    old_entry = self._get_entry(self.source, file_id)
 
1284
                    new_entry = self._get_entry(self.target, file_id)
 
1285
                    result, changes = self._changes_from_entries(
 
1286
                        old_entry, new_entry)
 
1287
                else:
 
1288
                    changes = True
 
1289
                # Get this parents parent to examine.
 
1290
                new_parent_id = result[4][1]
 
1291
                precise_file_ids.add(new_parent_id)
 
1292
                if changes:
 
1293
                    if (result[6][0] == 'directory' and
 
1294
                        result[6][1] != 'directory'):
 
1295
                        # This stopped being a directory, the old children have
 
1296
                        # to be included.
 
1297
                        if old_entry is None:
 
1298
                            # Reusing a discarded change.
 
1299
                            old_entry = self._get_entry(self.source, file_id)
 
1300
                        for child in old_entry.children.values():
 
1301
                            precise_file_ids.add(child.file_id)
 
1302
                    changed_file_ids.add(result[0])
 
1303
                    yield result
 
1304
 
 
1305
    @needs_read_lock
 
1306
    def file_content_matches(self, source_file_id, target_file_id,
 
1307
            source_path=None, target_path=None, source_stat=None, target_stat=None):
 
1308
        """Check if two files are the same in the source and target trees.
 
1309
 
 
1310
        This only checks that the contents of the files are the same,
 
1311
        it does not touch anything else.
 
1312
 
 
1313
        :param source_file_id: File id of the file in the source tree
 
1314
        :param target_file_id: File id of the file in the target tree
 
1315
        :param source_path: Path of the file in the source tree
 
1316
        :param target_path: Path of the file in the target tree
 
1317
        :param source_stat: Optional stat value of the file in the source tree
 
1318
        :param target_stat: Optional stat value of the file in the target tree
 
1319
        :return: Boolean indicating whether the files have the same contents
 
1320
        """
 
1321
        source_verifier_kind, source_verifier_data = self.source.get_file_verifier(
 
1322
            source_file_id, source_path, source_stat)
 
1323
        target_verifier_kind, target_verifier_data = self.target.get_file_verifier(
 
1324
            target_file_id, target_path, target_stat)
 
1325
        if source_verifier_kind == target_verifier_kind:
 
1326
            return (source_verifier_data == target_verifier_data)
 
1327
        # Fall back to SHA1 for now
 
1328
        if source_verifier_kind != "SHA1":
 
1329
            source_sha1 = self.source.get_file_sha1(source_file_id,
 
1330
                    source_path, source_stat)
 
1331
        else:
 
1332
            source_sha1 = source_verifier_data
 
1333
        if target_verifier_kind != "SHA1":
 
1334
            target_sha1 = self.target.get_file_sha1(target_file_id,
 
1335
                    target_path, target_stat)
 
1336
        else:
 
1337
            target_sha1 = target_verifier_data
 
1338
        return (source_sha1 == target_sha1)
 
1339
 
 
1340
InterTree.register_optimiser(InterTree)
1063
1341
 
1064
1342
 
1065
1343
class MultiWalker(object):