This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5594

copies: consider nullrev a common ancestor
ClosedPublic

Authored by martinvonz on Jan 15 2019, 7:27 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGb80af0707066: copies: consider nullrev a common ancestor
Summary

I've seen many bugs in the git codebase that were caused by it not
having a null revision and being forced to treat root commits
differently. Mercurial has a null revision and I think it's generally
a bug to treat it differently from other commits in graph algorithms.

This effectively undoes 83cfa1baf8ad (copies: don't report copies with
unrelated branch, 2010-01-01). The test cases that that commit added
still passes. I suspect some other fix after that commit made it
unnecessary.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

martinvonz created this revision.Jan 15 2019, 7:27 PM
yuja added a subscriber: yuja.Jan 18 2019, 7:14 AM
I've seen many bugs in the git codebase that were caused by it not
having a null revision and being forced to treat root commits
differently. Mercurial has a null revision and I think it's generally
a bug to treat it differently from other commits in graph algorithms.

I agree with that, but I don't think every non-merge revision (p2 = null)
should be considered a direct child of null revision.

@@ -65,8 +63,6 @@

else:
    parents = cl.parentrevs(r)

Here parents[1] may be nullrev. Is that expected?

for p in parents:
  • if p < 0:
  • continue
lothiraldan added a subscriber: lothiraldan.Jan 18 2019, 8:25 AM
In D5594#83078, @yuja wrote:
I've seen many bugs in the git codebase that were caused by it not
having a null revision and being forced to treat root commits
differently. Mercurial has a null revision and I think it's generally
a bug to treat it differently from other commits in graph algorithms.

I agree with that, but I don't think every non-merge revision (p2 = null)
should be considered a direct child of null revision.

@@ -65,8 +63,6 @@

else:
    parents = cl.parentrevs(r)

Here parents[1] may be nullrev. Is that expected?

for p in parents:
  • if p < 0:
  • continue

There are definitely repositories in the wild where p1 is nullrev (and p2 is not). It's unusual but expressable so, of course, it happened.

For that matters, there is also case with nullrev != p1 && p1 == p2.

yuja added a comment.Jan 18 2019, 9:01 AM
There are definitely repositories in the wild where p1 is nullrev (and p2 is not). It's unusual but expressable so, of course, it happened.
For that matters, there is also case with nullrev != p1 && p1 == p2.

Well, I think it should be considered a sort of corruption. context.py for
example would go wrong.

Maybe we can add some check to "hg verify".

martinvonz added a comment.Jan 24 2019, 6:56 PM
In D5594#83078, @yuja wrote:
I've seen many bugs in the git codebase that were caused by it not
having a null revision and being forced to treat root commits
differently. Mercurial has a null revision and I think it's generally
a bug to treat it differently from other commits in graph algorithms.

I agree with that, but I don't think every non-merge revision (p2 = null)
should be considered a direct child of null revision.

@@ -65,8 +63,6 @@

else:
    parents = cl.parentrevs(r)

Here parents[1] may be nullrev. Is that expected?

Oh, good catch! I'll fix that.

It seems like a more natural API to have parents() methods return only valid parents, but I suppose that may just be too large a change to make.

for p in parents:
  • if p < 0:
  • continue
martinvonz updated this revision to Diff 13434.Jan 24 2019, 6:57 PM
Closed by commit rHGb80af0707066: copies: consider nullrev a common ancestor (authored by martinvonz). · Explain WhyJan 26 2019, 2:10 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/copies.py (13 lines)

Diff 13232

mercurial/copies.py

def _findlimit(repo, a, b): def _findlimit(repo, a, b):
""" """
Find the last revision that needs to be checked to ensure that a full Find the last revision that needs to be checked to ensure that a full
transitive closure for file copies can be properly calculated. transitive closure for file copies can be properly calculated.
Generally, this means finding the earliest revision number that's an Generally, this means finding the earliest revision number that's an
ancestor of a or b but not both, except when a or b is a direct descendent ancestor of a or b but not both, except when a or b is a direct descendent
of the other, in which case we can return the minimum revnum of a and b. of the other, in which case we can return the minimum revnum of a and b.
None if no such revision exists.
""" """
# basic idea: # basic idea:
# - mark a and b with different sides # - mark a and b with different sides
# - if a parent's children are all on the same side, the parent is # - if a parent's children are all on the same side, the parent is
# on that side, otherwise it is on no side # on that side, otherwise it is on no side
# - walk the graph in topological order with the help of a heap; # - walk the graph in topological order with the help of a heap;
# - add unseen parents to side map # - add unseen parents to side map
# - clear side of any parent that has children on different sides # - clear side of any parent that has children on different sides
# - track number of interesting revs that might still be on a side # - track number of interesting revs that might still be on a side
# - track the lowest interesting rev seen # - track the lowest interesting rev seen
# - quit when interesting revs is zero # - quit when interesting revs is zero
cl = repo.changelog cl = repo.changelog
if a is None: if a is None:
a = node.wdirrev a = node.wdirrev
if b is None: if b is None:
b = node.wdirrev b = node.wdirrev
side = {a: -1, b: 1} side = {a: -1, b: 1}
visit = [-a, -b] visit = [-a, -b]
heapq.heapify(visit) heapq.heapify(visit)
interesting = len(visit) interesting = len(visit)
hascommonancestor = False
limit = node.wdirrev limit = node.wdirrev
while interesting: while interesting:
r = -heapq.heappop(visit) r = -heapq.heappop(visit)
if r == node.wdirrev: if r == node.wdirrev:
parents = [cl.rev(p) for p in repo.dirstate.parents()] parents = [cl.rev(p) for p in repo.dirstate.parents()]
else: else:
parents = cl.parentrevs(r) parents = cl.parentrevs(r)
for p in parents: for p in parents:
if p < 0:
continue
if p not in side: if p not in side:
# first time we see p; add it to visit # first time we see p; add it to visit
side[p] = side[r] side[p] = side[r]
if side[p]: if side[p]:
interesting += 1 interesting += 1
heapq.heappush(visit, -p) heapq.heappush(visit, -p)
elif side[p] and side[p] != side[r]: elif side[p] and side[p] != side[r]:
# p was interesting but now we know better # p was interesting but now we know better
side[p] = 0 side[p] = 0
interesting -= 1 interesting -= 1
hascommonancestor = True
if side[r]: if side[r]:
limit = r # lowest rev visited limit = r # lowest rev visited
interesting -= 1 interesting -= 1
if not hascommonancestor:
return None
# Consider the following flow (see test-commit-amend.t under issue4405): # Consider the following flow (see test-commit-amend.t under issue4405):
# 1/ File 'a0' committed # 1/ File 'a0' committed
# 2/ File renamed from 'a0' to 'a1' in a new commit (call it 'a1') # 2/ File renamed from 'a0' to 'a1' in a new commit (call it 'a1')
# 3/ Move back to first commit # 3/ Move back to first commit
# 4/ Create a new commit via revert to contents of 'a1' (call it 'a1-amend') # 4/ Create a new commit via revert to contents of 'a1' (call it 'a1-amend')
# 5/ Rename file from 'a1' to 'a2' and commit --amend 'a1-msg' # 5/ Rename file from 'a1' to 'a2' and commit --amend 'a1-msg'
# #
# During the amend in step five, we will be in this state: # During the amend in step five, we will be in this state:
# one-side-only changeset, but not further back than that # one-side-only changeset, but not further back than that
repo = a._repo repo = a._repo
debug = repo.ui.debugflag and repo.ui.configbool('devel', 'debug.copies') debug = repo.ui.debugflag and repo.ui.configbool('devel', 'debug.copies')
dbg = repo.ui.debug dbg = repo.ui.debug
if debug: if debug:
dbg('debug.copies: looking into rename from %s to %s\n' dbg('debug.copies: looking into rename from %s to %s\n'
% (a, b)) % (a, b))
limit = _findlimit(repo, a.rev(), b.rev()) limit = _findlimit(repo, a.rev(), b.rev())
if limit is None:
limit = node.nullrev
if debug: if debug:
dbg('debug.copies: search limit: %d\n' % limit) dbg('debug.copies: search limit: %d\n' % limit)
am = a.manifest() am = a.manifest()
# find where new files came from # find where new files came from
# we currently don't try to find where old files went, too expensive # we currently don't try to find where old files went, too expensive
# this means we can miss a case like 'hg rm b; hg cp a b' # this means we can miss a case like 'hg rm b; hg cp a b'
cm = {} cm = {}
dirtyc1 = not base.isancestorof(_c1) dirtyc1 = not base.isancestorof(_c1)
dirtyc2 = not base.isancestorof(_c2) dirtyc2 = not base.isancestorof(_c2)
graft = dirtyc1 or dirtyc2 graft = dirtyc1 or dirtyc2
tca = base tca = base
if graft: if graft:
tca = _c1.ancestor(_c2) tca = _c1.ancestor(_c2)
limit = _findlimit(repo, c1.rev(), c2.rev()) limit = _findlimit(repo, c1.rev(), c2.rev())
if limit is None:
# no common ancestor, no copies
return {}, {}, {}, {}, {}
repo.ui.debug(" searching for copies back to rev %d\n" % limit) repo.ui.debug(" searching for copies back to rev %d\n" % limit)
m1 = c1.manifest() m1 = c1.manifest()
m2 = c2.manifest() m2 = c2.manifest()
mb = base.manifest() mb = base.manifest()
# gather data from _checkcopies: # gather data from _checkcopies:
# - diverge = record all diverges in this dict # - diverge = record all diverges in this dict