comparison mercurial/dagop.py @ 44659:67f757ed86e0

dagop: fix subsetparentswalker to set p1/p2 chains at merge revision

The previous implementation was wrong because the '1'/'2' key would be
appended at a fork revision. Since we traverse the graph from heads, a merge
revision is actually a branching point, where the sort key must be generated.

44658:25436f83fb95

        # When a revision is visited, 'pointers[rev]' should be popped and
        # propagated to its parents accordingly.
        #
        # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes
        # 0 and 'parents[rev]' contains the unsorted list of parent revisions
        # and p1/p2 chains (excluding linear paths.)

        subset = self._subset
        tovisit = self._tovisit  # heap queue of [-rev]
        pendingcnt = self._pendingcnt  # {rev: count} for visited revisions
        pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}

                    parentpointers = [
                        (unresolved, resolved),
                        (unresolved.copy(), resolved.copy()),
                    ]
                    # 'rev' is a merge revision. increment the pending count
                    # as the 'unresolved' dict will be duplicated.
                    for r in unresolved:
                        pendingcnt[r] += 1
                for i, p in enumerate(parentrevs):
                    assert p < rev
                    heapq.heappush(tovisit, -p)
                    if p in pointers:
                        # 'p' is a fork revision. concatenate tracking pointers
                        # and decrement the pending count accordingly.
                        knownunresolved, knownresolved = pointers[p]
                        unresolved, resolved = parentpointers[i]
                        for r, c in unresolved.items():
                            c += [b'1', b'2'][i]
                            if r in knownunresolved:
                                # unresolved at both paths
                                pendingcnt[r] -= 1
                                assert pendingcnt[r] > 0
                                # take shorter chain

                        pointers[p] = parentpointers[i]

            # then, populate the active parents directly and add the current
            # 'rev' to the tracking pointers of the inactive parents.
            # 'pointers[p]' may be optimized out if both parents are active.
            if curactive and bothparentsactive:
                for i, p in enumerate(parentrevs):
                    c = [b'1', b'2'][i]
                    parents[rev].append((c, p))
                    # no need to mark 'rev' as resolved since the 'rev' should
                    # be fully resolved (i.e. pendingcnt[rev] == 0)
                assert pendingcnt[rev] == 0
            elif curactive:
                for i, p in enumerate(parentrevs):
                    unresolved, resolved = pointers[p]
                    assert rev not in unresolved
                    c = [b'1', b'2'][i]
                    if p in subset:
                        parents[rev].append((c, p))
                        # mark 'rev' as resolved through this path
                        resolved.add(rev)
                    else:

44659:67f757ed86e0

        # When a revision is visited, 'pointers[rev]' should be popped and
        # propagated to its parents accordingly.
        #
        # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes
        # 0 and 'parents[rev]' contains the unsorted list of parent revisions
        # and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be
        # used as a sort key preferring p1. 'len(chain)' should be the number
        # of merges between two revisions.

        subset = self._subset
        tovisit = self._tovisit  # heap queue of [-rev]
        pendingcnt = self._pendingcnt  # {rev: count} for visited revisions
        pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}

                    parentpointers = [
                        (unresolved, resolved),
                        (unresolved.copy(), resolved.copy()),
                    ]
                    # 'rev' is a merge revision. increment the pending count
                    # as the 'unresolved' dict will be duplicated, and append
                    # p1/p2 code to the existing chains.
                    for r in unresolved:
                        pendingcnt[r] += 1
                        parentpointers[0][0][r] += b'1'
                        parentpointers[1][0][r] += b'2'
                for i, p in enumerate(parentrevs):
                    assert p < rev
                    heapq.heappush(tovisit, -p)
                    if p in pointers:
                        # 'p' is a fork revision. concatenate tracking pointers
                        # and decrement the pending count accordingly.
                        knownunresolved, knownresolved = pointers[p]
                        unresolved, resolved = parentpointers[i]
                        for r, c in unresolved.items():
                            if r in knownunresolved:
                                # unresolved at both paths
                                pendingcnt[r] -= 1
                                assert pendingcnt[r] > 0
                                # take shorter chain

                        pointers[p] = parentpointers[i]

            # then, populate the active parents directly and add the current
            # 'rev' to the tracking pointers of the inactive parents.
            # 'pointers[p]' may be optimized out if both parents are active.
            chaincodes = [b''] if len(parentrevs) <= 1 else [b'1', b'2']
            if curactive and bothparentsactive:
                for i, p in enumerate(parentrevs):
                    c = chaincodes[i]
                    parents[rev].append((c, p))
                    # no need to mark 'rev' as resolved since the 'rev' should
                    # be fully resolved (i.e. pendingcnt[rev] == 0)
                assert pendingcnt[rev] == 0
            elif curactive:
                for i, p in enumerate(parentrevs):
                    unresolved, resolved = pointers[p]
                    assert rev not in unresolved
                    c = chaincodes[i]
                    if p in subset:
                        parents[rev].append((c, p))
                        # mark 'rev' as resolved through this path
                        resolved.add(rev)
                    else: