~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

• browse files at revision 3805.2.2
• compare with another revision
• download diff
• download tarball
• view history from revision 3805.2.2

• reverse the comparison (3805.2.2 to 3474)
• stop comparing with revision 3474

Show diffs side-by-side

added

removed

bzrlib/graph.py

766

766

            common_walker.start_searching(new_common)

767

767

        return candidate_heads

768

768

 

 

769

    def find_merge_order(self, tip_revision_id, lca_revision_ids):

 

770

        """Find the order that each revision was merged into tip.

 

771

 

 

772

        This basically just walks backwards with a stack, and walks left-first

 

773

        until it finds a node to stop.

 

774

        """

 

775

        if len(lca_revision_ids) == 1:

 

776

            return list(lca_revision_ids)

 

777

        looking_for = set(lca_revision_ids)

 

778

        # TODO: Is there a way we could do this "faster" by batching up the

 

779

        # get_parent_map requests?

 

780

        # TODO: Should we also be culling the ancestry search right away? We

 

781

        # could add looking_for to the "stop" list, and walk their

 

782

        # ancestry in batched mode. The flip side is it might mean we walk a

 

783

        # lot of "stop" nodes, rather than only the minimum.

 

784

        # Then again, without it we may trace back into ancestry we could have

 

785

        # stopped early.

 

786

        stack = [tip_revision_id]

 

787

        found = []

 

788

        stop = set()

 

789

        while stack and looking_for:

 

790

            next = stack.pop()

 

791

            stop.add(next)

 

792

            if next in looking_for:

 

793

                found.append(next)

 

794

                looking_for.remove(next)

 

795

                if len(looking_for) == 1:

 

796

                    found.append(looking_for.pop())

 

797

                    break

 

798

                continue

 

799

            parent_ids = self.get_parent_map([next]).get(next, None)

 

800

            if not parent_ids: # Ghost, nothing to search here

 

801

                continue

 

802

            for parent_id in reversed(parent_ids):

 

803

                # TODO: (performance) We see the parent at this point, but we

 

804

                #       wait to mark it until later to make sure we get left

 

805

                #       parents before right parents. However, instead of

 

806

                #       waiting until we have traversed enough parents, we

 

807

                #       could instead note that we've found it, and once all

 

808

                #       parents are in the stack, just reverse iterate the

 

809

                #       stack for them.

 

810

                if parent_id not in stop:

 

811

                    # this will need to be searched

 

812

                    stack.append(parent_id)

 

813

                stop.add(parent_id)

 

814

        return found

 

815

 

769

816

    def find_unique_lca(self, left_revision, right_revision,

770

817

                        count_steps=False):

771

818

        """Find a unique LCA.

1228

1275

        parent_map = self._parents_provider.get_parent_map(revisions)

1229

1276

        found_revisions.update(parent_map)

1230

1277

        for rev_id, parents in parent_map.iteritems():

 

1278

            if parents is None:

 

1279

                continue

1231

1280

            new_found_parents = [p for p in parents if p not in self.seen]

1232

1281

            if new_found_parents:

1233

1282

                # Calling set.update() with an empty generator is actually

1397

1446

        """

1398

1447

        return self._keys

1399

1448

 

 

1449

 

 

1450

def collapse_linear_regions(parent_map):

 

1451

    """Collapse regions of the graph that are 'linear'.

 

1452

 

 

1453

    For example::

 

1454

 

 

1455

      A:[B], B:[C]

 

1456

 

 

1457

    can be collapsed by removing B and getting::

 

1458

 

 

1459

      A:[C]

 

1460

 

 

1461

    :param parent_map: A dictionary mapping children to their parents

 

1462

    :return: Another dictionary with 'linear' chains collapsed

 

1463

    """

 

1464

    # Note: this isn't a strictly minimal collapse. For example:

 

1465

    #   A

 

1466

    #  / \

 

1467

    # B   C

 

1468

    #  \ /

 

1469

    #   D

 

1470

    #   |

 

1471

    #   E

 

1472

    # Will not have 'D' removed, even though 'E' could fit. Also:

 

1473

    #   A

 

1474

    #   |    A

 

1475

    #   B => |

 

1476

    #   |    C

 

1477

    #   C

 

1478

    # A and C are both kept because they are edges of the graph. We *could* get

 

1479

    # rid of A if we wanted.

 

1480

    #   A

 

1481

    #  / \

 

1482

    # B   C

 

1483

    # |   |

 

1484

    # D   E

 

1485

    #  \ /

 

1486

    #   F

 

1487

    # Will not have any nodes removed, even though you do have an

 

1488

    # 'uninteresting' linear D->B and E->C

 

1489

    children = {}

 

1490

    for child, parents in parent_map.iteritems():

 

1491

        children.setdefault(child, [])

 

1492

        for p in parents:

 

1493

            children.setdefault(p, []).append(child)

 

1494

 

 

1495

    orig_children = dict(children)

 

1496

    removed = set()

 

1497

    result = dict(parent_map)

 

1498

    for node in parent_map:

 

1499

        parents = result[node]

 

1500

        if len(parents) == 1:

 

1501

            parent_children = children[parents[0]]

 

1502

            if len(parent_children) != 1:

 

1503

                # This is not the only child

 

1504

                continue

 

1505

            node_children = children[node]

 

1506

            if len(node_children) != 1:

 

1507

                continue

 

1508

            child_parents = result.get(node_children[0], None)

 

1509

            if len(child_parents) != 1:

 

1510

                # This is not its only parent

 

1511

                continue

 

1512

            # The child of this node only points at it, and the parent only has

 

1513

            # this as a child. remove this node, and join the others together

 

1514

            result[node_children[0]] = parents

 

1515

            children[parents[0]] = node_children

 

1516

            del result[node]

 

1517

            del children[node]

 

1518

            removed.add(node)

 

1519

 

 

1520

    return result

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1