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

15

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

16

17

18

import errno

19

from itertools import chain

20

import os

21

import warnings

22

23

18

from bzrlib import (

19

branch as _mod_branch,

20

conflicts as _mod_conflicts,

24

21

debug,

25

22

errors,

26

23

graph as _mod_graph,

24

merge3,

27

25

osutils,

28

26

patiencediff,

27

progress,

29

28

registry,

30

29

revision as _mod_revision,

30

textfile,

31

trace,

32

transform,

31

33

tree as _mod_tree,

32

34

tsort,

35

ui,

36

versionedfile

33

37

)

34

from bzrlib.branch import Branch

35

from bzrlib.conflicts import ConflictList, Conflict

36

from bzrlib.errors import (BzrCommandError,

37

BzrError,

38

NoCommonAncestor,

39

NoCommits,

40

NoSuchRevision,

41

NoSuchFile,

42

NotBranchError,

43

NotVersionedError,

44

UnrelatedBranches,

45

UnsupportedOperation,

46

WorkingTreeNotRevision,

47

BinaryFile,

48

)

49

from bzrlib.graph import Graph

50

from bzrlib.merge3 import Merge3

51

from bzrlib.osutils import rename, pathjoin

52

from progress import DummyProgress, ProgressPhase

53

from bzrlib.revision import (NULL_REVISION, ensure_null)

54

from bzrlib.textfile import check_text_lines

55

from bzrlib.trace import mutter, warning, note, is_quiet

56

from bzrlib.transform import (TransformPreview, TreeTransform,

57

resolve_conflicts, cook_conflicts,

58

conflict_pass, FinalPaths, create_from_tree,

59

unique_add, ROOT_PARENT)

60

from bzrlib.versionedfile import PlanWeaveMerge

61

from bzrlib import ui

62

63

38

# TODO: Report back as changes are merged in

64

39

65

40

94

69

self.show_base = False

95

70

self.reprocess = False

96

71

if pb is None:

97

pb = DummyProgress()

72

pb = progress.DummyProgress()

98

73

self._pb = pb

99

74

self.pp = None

100

75

self.recurse = recurse

184

159

base_revision_id, tree.branch.last_revision())):

185

160

base_revision_id = None

186

161

else:

187

warning('Performing cherrypick')

162

trace.warning('Performing cherrypick')

188

163

merger = klass.from_revision_ids(pb, tree, other_revision_id,

189

164

base_revision_id, revision_graph=

190

165

revision_graph)

242

217

if revno is None:

243

218

tree = workingtree.WorkingTree.open_containing(location)[0]

244

219

return tree.branch, tree

245

branch = Branch.open_containing(location, possible_transports)[0]

220

branch = _mod_branch.Branch.open_containing(

221

location, possible_transports)[0]

246

222

if revno == -1:

247

223

revision_id = branch.last_revision()

248

224

else:

249

225

revision_id = branch.get_rev_id(revno)

250

revision_id = ensure_null(revision_id)

226

revision_id = _mod_revision.ensure_null(revision_id)

251

227

return branch, self.revision_tree(revision_id, branch)

252

228

253

229

def ensure_revision_trees(self):

271

247

if self.this_rev_id is None:

272

248

if self.this_basis_tree.get_file_sha1(file_id) != \

273

249

self.this_tree.get_file_sha1(file_id):

274

raise WorkingTreeNotRevision(self.this_tree)

250

raise errors.WorkingTreeNotRevision(self.this_tree)

275

251

276

252

trees = (self.this_basis_tree, self.other_tree)

277

253

return [get_id(tree, file_id) for tree in trees]

278

254

279

255

def check_basis(self, check_clean, require_commits=True):

280

256

if self.this_basis is None and require_commits is True:

281

raise BzrCommandError("This branch has no commits."

282

" (perhaps you would prefer 'bzr pull')")

257

raise errors.BzrCommandError(

258

"This branch has no commits."

259

" (perhaps you would prefer 'bzr pull')")

283

260

if check_clean:

284

261

self.compare_basis()

285

262

if self.this_basis != self.this_rev_id:

333

310

self.other_rev_id = _mod_revision.ensure_null(

334

311

self.other_branch.last_revision())

335

312

if _mod_revision.is_null(self.other_rev_id):

336

raise NoCommits(self.other_branch)

313

raise errors.NoCommits(self.other_branch)

337

314

self.other_basis = self.other_rev_id

338

315

elif other_revision[1] is not None:

339

316

self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])

342

319

self.other_rev_id = None

343

320

self.other_basis = self.other_branch.last_revision()

344

321

if self.other_basis is None:

345

raise NoCommits(self.other_branch)

322

raise errors.NoCommits(self.other_branch)

346

323

if self.other_rev_id is not None:

347

324

self._cached_trees[self.other_rev_id] = self.other_tree

348

325

self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)

375

352

target.fetch(source, revision_id)

376

353

377

354

def find_base(self):

378

revisions = [ensure_null(self.this_basis),

379

ensure_null(self.other_basis)]

380

if NULL_REVISION in revisions:

381

self.base_rev_id = NULL_REVISION

355

revisions = [_mod_revision.ensure_null(self.this_basis),

356

_mod_revision.ensure_null(self.other_basis)]

357

if _mod_revision.NULL_REVISION in revisions:

358

self.base_rev_id = _mod_revision.NULL_REVISION

382

359

self.base_tree = self.revision_tree(self.base_rev_id)

383

360

self._is_criss_cross = False

384

361

else:

385

362

lcas = self.revision_graph.find_lca(revisions[0], revisions[1])

386

363

self._is_criss_cross = False

387

364

if len(lcas) == 0:

388

self.base_rev_id = NULL_REVISION

365

self.base_rev_id = _mod_revision.NULL_REVISION

389

366

elif len(lcas) == 1:

390

367

self.base_rev_id = list(lcas)[0]

391

368

else: # len(lcas) > 1

400

377

self.base_rev_id = self.revision_graph.find_unique_lca(

401

378

*lcas)

402

379

self._is_criss_cross = True

403

if self.base_rev_id == NULL_REVISION:

404

raise UnrelatedBranches()

380

if self.base_rev_id == _mod_revision.NULL_REVISION:

381

raise errors.UnrelatedBranches()

405

382

if self._is_criss_cross:

406

warning('Warning: criss-cross merge encountered. See bzr'

407

' help criss-cross.')

408

mutter('Criss-cross lcas: %r' % lcas)

383

trace.warning('Warning: criss-cross merge encountered. See bzr'

384

' help criss-cross.')

385

trace.mutter('Criss-cross lcas: %r' % lcas)

409

386

interesting_revision_ids = [self.base_rev_id]

410

387

interesting_revision_ids.extend(lcas)

411

388

interesting_trees = dict((t.get_revision_id(), t)

421

398

self.base_tree = self.revision_tree(self.base_rev_id)

422

399

self.base_is_ancestor = True

423

400

self.base_is_other_ancestor = True

424

mutter('Base revid: %r' % self.base_rev_id)

401

trace.mutter('Base revid: %r' % self.base_rev_id)

425

402

426

403

def set_base(self, base_revision):

427

404

"""Set the base revision to use for the merge.

428

405

429

406

:param base_revision: A 2-list containing a path and revision number.

430

407

"""

431

mutter("doing merge() with no base_revision specified")

408

trace.mutter("doing merge() with no base_revision specified")

432

409

if base_revision == [None, None]:

433

410

self.find_base()

434

411

else:

454

431

if self.merge_type.supports_reprocess:

455

432

kwargs['reprocess'] = self.reprocess

456

433

elif self.reprocess:

457

raise BzrError("Conflict reduction is not supported for merge"

458

" type %s." % self.merge_type)

434

raise errors.BzrError(

435

"Conflict reduction is not supported for merge"

436

" type %s." % self.merge_type)

459

437

if self.merge_type.supports_show_base:

460

438

kwargs['show_base'] = self.show_base

461

439

elif self.show_base:

462

raise BzrError("Showing base is not supported for this"

463

" merge type. %s" % self.merge_type)

440

raise errors.BzrError("Showing base is not supported for this"

441

" merge type. %s" % self.merge_type)

464

442

if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)

465

443

and not self.base_is_other_ancestor):

466

444

raise errors.CannotReverseCherrypick()

515

493

finally:

516

494

self.this_tree.unlock()

517

495

if len(merge.cooked_conflicts) == 0:

518

if not self.ignore_zero and not is_quiet():

519

note("All changes applied successfully.")

496

if not self.ignore_zero and not trace.is_quiet():

497

trace.note("All changes applied successfully.")

520

498

else:

521

note("%d conflicts encountered." % len(merge.cooked_conflicts))

499

trace.note("%d conflicts encountered."

500

% len(merge.cooked_conflicts))

522

501

523

502

return len(merge.cooked_conflicts)

524

503

553

532

554

533

def __init__(self, working_tree, this_tree, base_tree, other_tree,

555

534

interesting_ids=None, reprocess=False, show_base=False,

556

pb=DummyProgress(), pp=None, change_reporter=None,

535

pb=progress.DummyProgress(), pp=None, change_reporter=None,

557

536

interesting_files=None, do_merge=True,

558

537

cherrypick=False, lca_trees=None):

559

538

"""Initialize the merger object and perform the merge.

605

584

self.change_reporter = change_reporter

606

585

self.cherrypick = cherrypick

607

586

if self.pp is None:

608

self.pp = ProgressPhase("Merge phase", 3, self.pb)

587

self.pp = progress.ProgressPhase("Merge phase", 3, self.pb)

609

588

if do_merge:

610

589

self.do_merge()

611

590

614

593

self.base_tree.lock_read()

615

594

self.other_tree.lock_read()

616

595

try:

617

self.tt = TreeTransform(self.this_tree, self.pb)

596

self.tt = transform.TreeTransform(self.this_tree, self.pb)

618

597

try:

619

598

self.pp.next_phase()

620

599

self._compute_transform()

623

602

self.write_modified(results)

624

603

try:

625

604

self.this_tree.add_conflicts(self.cooked_conflicts)

626

except UnsupportedOperation:

605

except errors.UnsupportedOperation:

627

606

pass

628

607

finally:

629

608

self.tt.finalize()

636

615

def make_preview_transform(self):

637

616

self.base_tree.lock_read()

638

617

self.other_tree.lock_read()

639

self.tt = TransformPreview(self.this_tree)

618

self.tt = transform.TransformPreview(self.this_tree)

640

619

try:

641

620

self.pp.next_phase()

642

621

self._compute_transform()

672

651

self.pp.next_phase()

673

652

child_pb = ui.ui_factory.nested_progress_bar()

674

653

try:

675

fs_conflicts = resolve_conflicts(self.tt, child_pb,

676

lambda t, c: conflict_pass(t, c, self.other_tree))

654

fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,

655

lambda t, c: transform.conflict_pass(t, c, self.other_tree))

677

656

finally:

678

657

child_pb.finished()

679

658

if self.change_reporter is not None:

682

661

self.tt.iter_changes(), self.change_reporter)

683

662

self.cook_conflicts(fs_conflicts)

684

663

for conflict in self.cooked_conflicts:

685

warning(conflict)

664

trace.warning(conflict)

686

665

687

666

def _entries3(self):

688

667

"""Gather data about files modified between three trees.

890

869

def fix_root(self):

891

870

try:

892

871

self.tt.final_kind(self.tt.root)

893

except NoSuchFile:

872

except errors.NoSuchFile:

894

873

self.tt.cancel_deletion(self.tt.root)

895

874

if self.tt.final_file_id(self.tt.root) is None:

896

875

self.tt.version_file(self.tt.tree_file_id(self.tt.root),

903

882

return

904

883

try:

905

884

self.tt.final_kind(other_root)

906

except NoSuchFile:

885

except errors.NoSuchFile:

907

886

return

908

887

if self.other_tree.inventory.root.file_id in self.this_tree.inventory:

909

888

# the other tree's root is a non-root in the current tree

1162

1141

self.tt.delete_contents(trans_id)

1163

1142

if file_id in self.other_tree:

1164

1143

# OTHER changed the file

1165

create_from_tree(self.tt, trans_id,

1166

self.other_tree, file_id)

1144

transform.create_from_tree(self.tt, trans_id,

1145

self.other_tree, file_id)

1167

1146

if not file_in_this:

1168

1147

self.tt.version_file(file_id, trans_id)

1169

1148

return "modified"

1180

1159

# have agreement that output should be a file.

1181

1160

try:

1182

1161

self.text_merge(file_id, trans_id)

1183

except BinaryFile:

1162

except errors.BinaryFile:

1184

1163

return contents_conflict()

1185

1164

if file_id not in self.this_tree:

1186

1165

self.tt.version_file(file_id, trans_id)

1187

1166

try:

1188

1167

self.tt.tree_kind(trans_id)

1189

1168

self.tt.delete_contents(trans_id)

1190

except NoSuchFile:

1169

except errors.NoSuchFile:

1191

1170

pass

1192

1171

return "modified"

1193

1172

else:

1211

1190

base_lines = []

1212

1191

other_lines = self.get_lines(self.other_tree, file_id)

1213

1192

this_lines = self.get_lines(self.this_tree, file_id)

1214

m3 = Merge3(base_lines, this_lines, other_lines,

1215

is_cherrypick=self.cherrypick)

1193

m3 = merge3.Merge3(base_lines, this_lines, other_lines,

1194

is_cherrypick=self.cherrypick)

1216

1195

start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"

1217

1196

if self.show_base is True:

1218

1197

base_marker = '|' * 7

1273

1252

"""Emit a single conflict file."""

1274

1253

name = name + '.' + suffix

1275

1254

trans_id = self.tt.create_path(name, parent_id)

1276

create_from_tree(self.tt, trans_id, tree, file_id, lines)

1255

transform.create_from_tree(self.tt, trans_id, tree, file_id, lines)

1277

1256

return trans_id

1278

1257

1279

1258

def merge_executable(self, file_id, file_status):

1303

1282

try:

1304

1283

if self.tt.final_kind(trans_id) != "file":

1305

1284

return

1306

except NoSuchFile:

1285

except errors.NoSuchFile:

1307

1286

return

1308

1287

if winner == "this":

1309

1288

executability = this_executable

1320

1299

1321

1300

def cook_conflicts(self, fs_conflicts):

1322

1301

"""Convert all conflicts into a form that doesn't depend on trans_id"""

1323

from conflicts import Conflict

1324

1302

name_conflicts = {}

1325

self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))

1326

fp = FinalPaths(self.tt)

1303

self.cooked_conflicts.extend(transform.cook_conflicts(

1304

fs_conflicts, self.tt))

1305

fp = transform.FinalPaths(self.tt)

1327

1306

for conflict in self._raw_conflicts:

1328

1307

conflict_type = conflict[0]

1329

1308

if conflict_type in ('name conflict', 'parent conflict'):

1331

1310

conflict_args = conflict[2:]

1332

1311

if trans_id not in name_conflicts:

1333

1312

name_conflicts[trans_id] = {}

1334

unique_add(name_conflicts[trans_id], conflict_type,

1335

conflict_args)

1313

transform.unique_add(name_conflicts[trans_id], conflict_type,

1314

conflict_args)

1336

1315

if conflict_type == 'contents conflict':

1337

1316

for trans_id in conflict[1]:

1338

1317

file_id = self.tt.final_file_id(trans_id)

1343

1322

if path.endswith(suffix):

1344

1323

path = path[:-len(suffix)]

1345

1324

break

1346

c = Conflict.factory(conflict_type, path=path, file_id=file_id)

1325

c = _mod_conflicts.Conflict.factory(conflict_type,

1326

path=path, file_id=file_id)

1347

1327

self.cooked_conflicts.append(c)

1348

1328

if conflict_type == 'text conflict':

1349

1329

trans_id = conflict[1]

1350

1330

path = fp.get_path(trans_id)

1351

1331

file_id = self.tt.final_file_id(trans_id)

1352

c = Conflict.factory(conflict_type, path=path, file_id=file_id)

1332

c = _mod_conflicts.Conflict.factory(conflict_type,

1333

path=path, file_id=file_id)

1353

1334

self.cooked_conflicts.append(c)

1354

1335

1355

1336

for trans_id, conflicts in name_conflicts.iteritems():

1370

1351

if this_parent is not None and this_name is not None:

1371

1352

this_parent_path = \

1372

1353

fp.get_path(self.tt.trans_id_file_id(this_parent))

1373

this_path = pathjoin(this_parent_path, this_name)

1354

this_path = osutils.pathjoin(this_parent_path, this_name)

1374

1355

else:

1375

1356

this_path = "<deleted>"

1376

1357

file_id = self.tt.final_file_id(trans_id)

1377

c = Conflict.factory('path conflict', path=this_path,

1378

conflict_path=other_path, file_id=file_id)

1358

c = _mod_conflicts.Conflict.factory('path conflict', path=this_path,

1359

conflict_path=other_path,

1360

file_id=file_id)

1379

1361

self.cooked_conflicts.append(c)

1380

self.cooked_conflicts.sort(key=Conflict.sort_key)

1362

self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)

1381

1363

1382

1364

1383

1365

class WeaveMerger(Merge3Merger):

1404

1386

name = self.tt.final_name(trans_id) + '.plan'

1405

1387

contents = ('%10s|%s' % l for l in plan)

1406

1388

self.tt.new_file(name, self.tt.final_parent(trans_id), contents)

1407

textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',

1408

'>>>>>>> MERGE-SOURCE\n')

1389

textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',

1390

'>>>>>>> MERGE-SOURCE\n')

1409

1391

return textmerge.merge_lines(self.reprocess)

1410

1392

1411

1393

def text_merge(self, file_id, trans_id):

1417

1399

lines = list(lines)

1418

1400

# Note we're checking whether the OUTPUT is binary in this case,

1419

1401

# because we don't want to get into weave merge guts.

1420

check_text_lines(lines)

1402

textfile.check_text_lines(lines)

1421

1403

self.tt.create_file(lines, trans_id)

1422

1404

if conflicts:

1423

1405

self._raw_conflicts.append(('text conflict', trans_id))

1447

1429

name = self.tt.final_name(trans_id) + '.plan'

1448

1430

contents = ('%10s|%s' % l for l in plan)

1449

1431

self.tt.new_file(name, self.tt.final_parent(trans_id), contents)

1450

textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',

1451

'>>>>>>> MERGE-SOURCE\n')

1432

textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',

1433

'>>>>>>> MERGE-SOURCE\n')

1452

1434

return textmerge.merge_lines(self.reprocess)

1453

1435

1454

1436

1456

1438

"""Three-way merger using external diff3 for text merging"""

1457

1439

1458

1440

def dump_file(self, temp_dir, name, tree, file_id):

1459

out_path = pathjoin(temp_dir, name)

1441

out_path = osutils.pathjoin(temp_dir, name)

1460

1442

out_file = open(out_path, "wb")

1461

1443

try:

1462

1444

in_file = tree.get_file(file_id)

1474

1456

import bzrlib.patch

1475

1457

temp_dir = osutils.mkdtemp(prefix="bzr-")

1476

1458

try:

1477

new_file = pathjoin(temp_dir, "new")

1459

new_file = osutils.pathjoin(temp_dir, "new")

1478

1460

this = self.dump_file(temp_dir, "this", self.this_tree, file_id)

1479

1461

base = self.dump_file(temp_dir, "base", self.base_tree, file_id)

1480

1462

other = self.dump_file(temp_dir, "other", self.other_tree, file_id)

1481

1463

status = bzrlib.patch.diff3(new_file, this, base, other)

1482

1464

if status not in (0, 1):

1483

raise BzrError("Unhandled diff3 exit code")

1465

raise errors.BzrError("Unhandled diff3 exit code")

1484

1466

f = open(new_file, 'rb')

1485

1467

try:

1486

1468

self.tt.create_file(f, trans_id)

1504

1486

other_rev_id=None,

1505

1487

interesting_files=None,

1506

1488

this_tree=None,

1507

pb=DummyProgress(),

1489

pb=progress.DummyProgress(),

1508

1490

change_reporter=None):

1509

1491

"""Primary interface for merging.

1510

1492

1513

1495

branch.get_revision_tree(base_revision))'

1514

1496

"""

1515

1497

if this_tree is None:

1516

raise BzrError("bzrlib.merge.merge_inner requires a this_tree "

1517

"parameter as of bzrlib version 0.8.")

1498

raise errors.BzrError("bzrlib.merge.merge_inner requires a this_tree "

1499

"parameter as of bzrlib version 0.8.")

1518

1500

merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,

1519

1501

pb=pb, change_reporter=change_reporter)

1520

1502

merger.backup_files = backup_files

1738

1720

super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)

1739

1721

self.a_key = self._key_prefix + (self.a_rev,)

1740

1722

self.b_key = self._key_prefix + (self.b_rev,)

1741

self.graph = Graph(self.vf)

1723

self.graph = _mod_graph.Graph(self.vf)

1742

1724

heads = self.graph.heads((self.a_key, self.b_key))

1743

1725

if len(heads) == 1:

1744

1726

# one side dominates, so we can just return its values, yay for

1749

1731

other = b_rev

1750

1732

else:

1751

1733

other = a_rev

1752

mutter('found dominating revision for %s\n%s > %s', self.vf,

1753

self._head_key[-1], other)

1734

trace.mutter('found dominating revision for %s\n%s > %s', self.vf,

1735

self._head_key[-1], other)

1754

1736

self._weave = None

1755

1737

else:

1756

1738

self._head_key = None

1770

1752

while True:

1771

1753

next_lcas = self.graph.find_lca(*cur_ancestors)

1772

1754

# Map a plain NULL_REVISION to a simple no-ancestors

1773

if next_lcas == set([NULL_REVISION]):

1755

if next_lcas == set([_mod_revision.NULL_REVISION]):

1774

1756

next_lcas = ()

1775

1757

# Order the lca's based on when they were merged into the tip

1776

1758

# While the actual merge portion of weave merge uses a set() of

1788

1770

elif len(next_lcas) > 2:

1789

1771

# More than 2 lca's, fall back to grabbing all nodes between

1790

1772

# this and the unique lca.

1791

mutter('More than 2 LCAs, falling back to all nodes for:'

1792

' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)

1773

trace.mutter('More than 2 LCAs, falling back to all nodes for:'

1774

' %s, %s\n=> %s',

1775

self.a_key, self.b_key, cur_ancestors)

1793

1776

cur_lcas = next_lcas

1794

1777

while len(cur_lcas) > 1:

1795

1778

cur_lcas = self.graph.find_lca(*cur_lcas)

1798

1781

unique_lca = None

1799

1782

else:

1800

1783

unique_lca = list(cur_lcas)[0]

1801

if unique_lca == NULL_REVISION:

1784

if unique_lca == _mod_revision.NULL_REVISION:

1802

1785

# find_lca will return a plain 'NULL_REVISION' rather

1803

1786

# than a key tuple when there is no common ancestor, we

1804

1787

# prefer to just use None, because it doesn't confuse

1827

1810

# We remove NULL_REVISION because it isn't a proper tuple key, and

1828

1811

# thus confuses things like _get_interesting_texts, and our logic

1829

1812

# to add the texts into the memory weave.

1830

if NULL_REVISION in parent_map:

1831

parent_map.pop(NULL_REVISION)

1813

if _mod_revision.NULL_REVISION in parent_map:

1814

parent_map.pop(_mod_revision.NULL_REVISION)

1832

1815

else:

1833

1816

interesting = set()

1834

1817

for tip in tip_keys:

1986

1969

lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))

1987

1970

self.lcas = set()

1988

1971

for lca in lcas:

1989

if lca == NULL_REVISION:

1972

if lca == _mod_revision.NULL_REVISION:

1990

1973

self.lcas.add(lca)

1991

1974

else:

1992

1975

self.lcas.add(lca[-1])