← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tree.py

various notes about find_ids_across_trees

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tree.py
404
404
    """
405
405
    if not filenames:
406
406
        return None
407
 
    specified_ids = _find_filename_ids_across_trees(filenames, trees, 
408
 
                                                    require_versioned)
409
 
    return _find_children_across_trees(specified_ids, trees)
410
 
 
411
 
 
412
 
def _find_filename_ids_across_trees(filenames, trees, require_versioned):
 
407
    specified_path_ids = _find_ids_across_trees(filenames, trees,
 
408
        require_versioned)
 
409
    return _find_children_across_trees(specified_path_ids, trees)
 
410
#    specified_ids = [id for path, id in _find_path_ids_across_trees(filenames, trees, require_versioned)]
 
411
#    return _find_children_across_trees(specified_ids, trees)
 
412
 
 
413
def find_path_ids_across_trees(filenames, trees, require_versioned=True):
 
414
    """Find the paths and ids corresponding to specified filenames.
 
415
    
 
416
    All matches in all trees will be used, and all children of matched
 
417
    directories will be included
 
418
 
 
419
    :param filenames: The filenames to find file_ids for
 
420
    :param trees: The trees to find file_ids within
 
421
    :param require_versioned: if true, all specified filenames must occur in
 
422
        at least one tree.
 
423
    :return: a set of (path, file ids) for the specified filenames and their
 
424
        children. The returned path is the path of the id in the first tree
 
425
        that contains it. This matters when files have been moved 
 
426
    """
 
427
    if not filenames:
 
428
        return set()
 
429
    # This function needs to know the ids for filenames in all trees, then
 
430
    # search for those same files and children in all the other trees.
 
431
    # it is complicated by the same path in two trees being able to have
 
432
    # different ids, which might both be present in both trees.
 
433
    # consider two trees, which have had 'mv foo bar' and 'mv baz foo' done
 
434
    # in this case, a diff of 'foo' should should changes to both the current
 
435
    # 'bar' and the current 'foo' which was baz. Its arguable that if 
 
436
    # the situation is 'mv parent/foo bar' and 'mv baz parent/foo', that 
 
437
    # we should return the current bar and the current parent/foo' - at the 
 
438
    # moment we do, but we loop around all ids and all trees: I*T checks.
 
439
    
 
440
    # Updating this algorithm to be fast in the common case:
 
441
    # nothing has moved, all files have the same id in parent, child and there
 
442
    # are only two trees (or one is working tree and the others are parents).
 
443
    # walk the dirstate. as we find each path, gather the paths of that
 
444
    # id in all trees. add a mapping from the id to the path in those trees.
 
445
    # now lookup children by id, again in all trees; for these trees that
 
446
    # nothing has moved in, the id->path mapping will allow us to find the
 
447
    # parent trivially. To answer 'has anything been moved' in one of the
 
448
    # dirstate parent trees though, we will need to stare harder at it.
 
449
 
 
450
    #  Now, given a path index, that is trivial for any one tree, and given
 
451
    #  that we can ask for additional data from a dirstate tree, its a single
 
452
    #  pass, though it will require scanning the entire tree to find paths
 
453
    #  that were at the current location.
 
454
    # ideal results?: There are three things: tree, path, id. Pathologically
 
455
    # we can have completely disjoint ids for each tree; but we cannot have 
 
456
    # disjoin paths for each tree, except if we scan each tree for the 
 
457
    # different ids from other trees.
 
458
 
 
459
    specified_path_ids = _find_ids_across_trees(filenames, trees,
 
460
        require_versioned)
 
461
    return _find_path_id_children_across_trees(specified_path_ids, trees)
 
462
 
 
463
 
 
464
def _find_ids_across_trees(filenames, trees, require_versioned):
413
465
    """Find the ids corresponding to specified filenames.
414
466
    
415
 
    All matches in all trees will be used.
 
467
    All matches in all trees will be used, but subdirectories are not scanned.
416
468
 
417
469
    :param filenames: The filenames to find file_ids for
418
470
    :param trees: The trees to find file_ids within
419
471
    :param require_versioned: if true, all specified filenames must occur in
420
 
    at least one tree.
421
 
    :return: a set of file ids for the specified filenames
 
472
        at least one tree.
 
473
    :return: a set of (path, file ids) for the specified filenames
422
474
    """
423
475
    not_versioned = []
424
476
    interesting_ids = set()
425
477
    for tree_path in filenames:
426
478
        not_found = True
427
479
        for tree in trees:
428
 
            file_id = tree.inventory.path2id(tree_path)
 
480
            file_id = tree.path2id(tree_path)
429
481
            if file_id is not None:
430
482
                interesting_ids.add(file_id)
431
483
                not_found = False
452
504
        new_pending = set()
453
505
        for file_id in pending:
454
506
            for tree in trees:
455
 
                if file_id not in tree:
 
507
                if not tree.has_id(file_id):
456
508
                    continue
457
509
                entry = tree.inventory[file_id]
458
510
                for child in getattr(entry, 'children', {}).itervalues():
494
546
            supplied and True all the 'specific_files' must be versioned, or
495
547
            a PathsNotVersionedError will be thrown.
496
548
        """
497
 
        # NB: show_status depends on being able to pass in non-versioned files and
498
 
        # report them as unknown
 
549
        # NB: show_status depends on being able to pass in non-versioned files
 
550
        # and report them as unknown
499
551
        trees = (self.source, self.target)
500
552
        if extra_trees is not None:
501
553
            trees = trees + tuple(extra_trees)