~bzr-pqm/bzr/bzr.dev : revision 3170.3.2

192

__slots__ = ['_node_name_stack',

193

'_node_merge_depth_stack',

194

'_pending_parents_stack',

195

'_assigned_sequence_stack',

195

'_first_child_stack',

196

'_left_subtree_pushed_stack',

197

'_generate_revno',

198

'_graph',

200

'_stop_revision',

201

'_original_graph',

202

'_revnos',

203

'_root_sequence',

203

'_revno_to_branch_count',

204

'_completed_node_names',

205

'_scheduled_nodes',

206

]

362

self._original_graph = dict(self._graph.items())

363

# we need to know the revision numbers of revisions to determine

364

# the revision numbers of their descendants

365

# this is a graph from node to [revno_tuple, sequence_number]

366

# where sequence is the number of branches made from the node,

365

# this is a graph from node to [revno_tuple, first_child]

366

# where first_child is True if no other children have seen this node

367

# and revno_tuple is the tuple that was assigned to the node.

368

# we dont know revnos to start with, so we start it seeded with

369

# [None, 0]

370

self._revnos = dict((revision, [None, 0]) for revision in self._graph)

371

# the global implicit root node has revno 0, but we need to know

372

# the sequence number for it too:

373

self._root_sequence = 0

369

# [None, True]

370

self._revnos = dict((revision, [None, True])

371

for revision in self._graph)

372

# Each mainline revision counts how many child branches have spawned from it.

373

self._revno_to_branch_count = {}

374

375

# this is a stack storing the depth first search into the graph.

376

self._node_name_stack = []

382

self._pending_parents_stack = []

383

# When we first look at a node we assign it a seqence number from its

384

# leftmost parent.

385

self._assigned_sequence_stack = []

385

self._first_child_stack = []

386

# this is a set of the nodes who have been completely analysed for fast

387

# membership checking

388

self._completed_node_names = set()

439

node_merge_depth_stack_append=node_merge_depth_stack.append,

440

left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,

441

pending_parents_stack_append=pending_parents_stack.append,

442

assigned_sequence_stack_append=self._assigned_sequence_stack.append,

443

original_graph=self._original_graph,

442

first_child_stack_append=self._first_child_stack.append,

444

443

revnos=self._revnos,

445

444

):

446

445

"""Add node_name to the pending node stack.

455

454

node_merge_depth_stack_append(merge_depth)

456

455

left_subtree_pushed_stack_append(False)

457

456

pending_parents_stack_append(list(parents))

458

# as we push it, assign it a sequence number against its parent:

459

parents = original_graph[node_name]

457

# as we push it, check if it is the first child

460

458

if parents:

461

459

# node has parents, assign from the left most parent.

462

parent_revno = revnos[parents[0]]

463

sequence = parent_revno[1]

464

parent_revno[1] += 1

460

parent_info = revnos[parents[0]]

461

first_child = parent_info[1]

462

parent_info[1] = False

465

463

else:

466

# no parents, use the root sequence

467

sequence = self._root_sequence

468

self._root_sequence +=1

469

assigned_sequence_stack_append(sequence)

464

# We don't use the same algorithm here, but we need to keep the

465

# stack in line

466

first_child = None

467

first_child_stack_append(first_child)

470

468

471

469

def pop_node(node_name_stack_pop=node_name_stack.pop,

472

470

node_merge_depth_stack_pop=node_merge_depth_stack.pop,

473

assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,

471

first_child_stack_pop=self._first_child_stack.pop,

474

472

left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,

475

473

pending_parents_stack_pop=pending_parents_stack.pop,

476

474

original_graph=self._original_graph,

477

475

revnos=self._revnos,

478

476

completed_node_names_add=self._completed_node_names.add,

479

477

scheduled_nodes_append=scheduled_nodes.append,

478

revno_to_branch_count=self._revno_to_branch_count,

480

479

):

481

480

"""Pop the top node off the stack

482

481

486

485

# pop off the local variables

487

486

node_name = node_name_stack_pop()

488

487

merge_depth = node_merge_depth_stack_pop()

489

sequence = assigned_sequence_stack_pop()

488

first_child = first_child_stack_pop()

490

489

# remove this node from the pending lists:

491

490

left_subtree_pushed_stack_pop()

492

491

pending_parents_stack_pop()

494

493

parents = original_graph[node_name]

495

494

if parents:

496

495

# node has parents, assign from the left most parent.

497

parent_revno = revnos[parents[0]]

498

if sequence:

496

parent_revno = revnos[parents[0]][0]

497

if not first_child:

499

498

# not the first child, make a new branch

500

revno = parent_revno[0] + (sequence, 1)

499

base_revno = parent_revno[0]

500

branch_count = revno_to_branch_count.get(base_revno, 0)

501

branch_count += 1

502

revno_to_branch_count[base_revno] = branch_count

503

revno = (parent_revno[0], branch_count, 1)

504

# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)

501

505

else:

502

# increment the sequence number within the branch

503

revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)

506

# as the first child, we just increase the final revision

507

# number

508

revno = parent_revno[:-1] + (parent_revno[-1] + 1,)

504

509

else:

505

510

# no parents, use the root sequence

506

if sequence:

507

# make a parallel import revision number

508

revno = (0, sequence, 1)

511

root_count = revno_to_branch_count.get(0, 0)

512

if root_count:

513

revno = (0, root_count, 1)

509

514

else:

510

515

revno = (1,)

516

root_count += 1

517

revno_to_branch_count[0] = root_count

511

518

512

519

# store the revno for this node for future reference

513

520

revnos[node_name][0] = revno

610

617

self._node_merge_depth_stack.append(merge_depth)

611

618

self._left_subtree_pushed_stack.append(False)

612

619

self._pending_parents_stack.append(list(parents))

613

# as we push it, assign it a sequence number against its parent:

620

# as we push it, figure out if this is the first child

614

621

parents = self._original_graph[node_name]

615

622

if parents:

616

623

# node has parents, assign from the left most parent.

617

parent_revno = self._revnos[parents[0]]

618

sequence = parent_revno[1]

619

parent_revno[1] += 1

624

parent_info = self._revnos[parents[0]]

625

first_child = parent_info[1]

626

parent_info[1] = False

620

627

else:

621

# no parents, use the root sequence

622

sequence = self._root_sequence

623

self._root_sequence +=1

624

self._assigned_sequence_stack.append(sequence)

628

# We don't use the same algorithm here, but we need to keep the

629

# stack in line

630

first_child = None

631

self._first_child_stack.append(first_child)

625

632

626

633

def _pop_node(self):

627

634

"""Pop the top node off the stack

632

639

# pop off the local variables

633

640

node_name = self._node_name_stack.pop()

634

641

merge_depth = self._node_merge_depth_stack.pop()

635

sequence = self._assigned_sequence_stack.pop()

642

first_child = self._first_child_stack.pop()

636

643

# remove this node from the pending lists:

637

644

self._left_subtree_pushed_stack.pop()

638

645

self._pending_parents_stack.pop()

640

647

parents = self._original_graph[node_name]

641

648

if parents:

642

649

# node has parents, assign from the left most parent.

643

parent_revno = self._revnos[parents[0]]

644

if sequence:

650

parent_revno = self._revnos[parents[0]][0]

651

if not first_child:

645

652

# not the first child, make a new branch

646

revno = parent_revno[0] + (sequence, 1)

653

base_revno = parent_revno[0]

654

branch_count = self._revno_to_branch_count.get(base_revno, 0)

655

branch_count += 1

656

self._revno_to_branch_count[base_revno] = branch_count

657

revno = (parent_revno[0], branch_count, 1)

658

# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)

647

659

else:

648

# increment the sequence number within the branch

649

revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)

660

# as the first child, we just increase the final revision

661

# number

662

revno = parent_revno[:-1] + (parent_revno[-1] + 1,)

650

663

else:

651

664

# no parents, use the root sequence

652

if sequence:

653

# make a parallel import revision number

654

revno = (0, sequence, 1)

665

root_count = self._revno_to_branch_count.get(0, 0)

666

if root_count:

667

revno = (0, root_count, 1)

655

668

else:

656

669

revno = (1,)

670

root_count += 1

671

self._revno_to_branch_count[0] = root_count

657

672

658

673

# store the revno for this node for future reference

659

674

self._revnos[node_name][0] = revno