~bzr-pqm/bzr/bzr.dev

Viewing changes to bzrlib/_known_graph_pyx.pyx

Committer: John Arbash Meinel
Date: 2009-08-17 16:35:07 UTC
mto: This revision was merged to the branch mainline in revision 4629.
Revision ID: john@arbash-meinel.com-20090817163507-0j9tdamcybwqu8rn

Add tests that we detect GraphCycleError

Turned out to be quite important, because otherwise KnownGraph.merge_sort()
ends up in an infinite loop w/ a GraphCycle.
(unlike topo_sort which pretty much just ignores those nodes.)

files modified:
bzrlib/_known_graph_py.py

bzrlib/_known_graph_pyx.pyx

bzrlib/tests/test__known_graph.py

bzrlib/tsort.py

Show diffs side-by-side

added added

removed removed

bzrlib/_known_graph_pyx.pyx

448

return 0

449

450

451

# cdef _MergeSortNode _get_ms_node(lst, Py_ssize_t pos):

452

# cdef PyObject *temp_node

453

454

# temp_node = PyList_GET_ITEM(lst, pos)

455

# return <_MergeSortNode>temp_node

456

457

458

451

cdef class _MergeSorter:

459

452

"""This class does the work of computing the merge_sort ordering.

460

453

463

456

"""

464

457

465

458

# Current performance numbers for merge_sort(bzr_dev_parent_map):

466

# 310ms tsort.merge_sort()

467

# 92ms graph.KnownGraph().merge_sort()

468

# 42ms kg.merge_sort()

459

# 302ms tsort.merge_sort()

460

# 91ms graph.KnownGraph().merge_sort()

461

# 41ms kg.merge_sort()

469

462

470

463

cdef KnownGraph graph

471

464

cdef object _depth_first_stack # list

537

530

cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node

538

531

cdef _KnownGraphNode node, parent_node, prev_node

539

532

540

assert self._last_stack_item >= 0

541

533

node = _get_list_node(self._depth_first_stack, self._last_stack_item)

542

534

ms_node = <_MergeSortNode>node.extra

543

535

self._last_stack_item = self._last_stack_item - 1

616

608

# print ' ', self._scheduled_nodes

617

609

last_node = _get_list_node(self._depth_first_stack,

618

610

self._last_stack_item)

611

if last_node.gdfo == -1:

612

raise errors.GraphCycleError(self.graph._nodes)

619

613

ms_last_node = <_MergeSortNode>last_node.extra

620

614

if not ms_last_node.has_pending_parents():

621

615

# Processed all parents, pop this node

653

647

## # this indicates a cycle.

654

648

## raise errors.GraphCycleError(self._depth_first_stack)

655

649

656

assert ms_next_node is not None

657

650

if next_node is ms_last_node.left_parent:

658

651

next_merge_depth = ms_last_node.merge_depth

659

652

else:

674

667

675

668

# We've set up the basic schedule, now we can continue processing the

676

669

# output.

677

# TODO: This final loop costs us 41.4ms => 28.3ms (13ms, 30%) on

670

# TODO: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on

678

671

# bzr.dev, to convert the internal Object representation into a

679

672

# Tuple representation...

680

673

# 2ms is walking the data and computing revno tuples

689

682

ms_node = <_MergeSortNode>node.extra

690

683

if ms_node.revno_first == -1:

691

684

if ms_node.revno_second != -1:

692

raise ValueError('Something wrong with: %s' % (ms_node,))

685

raise RuntimeError('Something wrong with: %s' % (ms_node,))

693

686

revno = (ms_node.revno_last,)

694

687

else:

695

688

revno = (ms_node.revno_first, ms_node.revno_second,

696

689

ms_node.revno_last)

697

t = (sequence_number, node.key,

698

ms_node.merge_depth, revno,

699

ms_node.end_of_merge)

700

PyList_Append(ordered, t)

701

# PyList_Append(ordered, )

690

PyList_Append(ordered, (sequence_number, node.key,

691

ms_node.merge_depth, revno,

692

ms_node.end_of_merge))

702

693

# Get rid of the extra stored info

703

694

node.extra = None

704

695

sequence_number = sequence_number + 1

Older »