mercurial/copies.py
author Matt Mackall <mpm@selenic.com>
Fri, 30 Dec 2011 15:07:05 -0600
branchstable
changeset 15749 6b84cdcb05b9
parent 14494 1ffeeb91c55d
child 15774 0bd17a4bed88
permissions -rw-r--r--
fetch: fix unneeded commit when no merge attempted (issue2847)
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     1
# copies.py - copy detection for Mercurial
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2008 Matt Mackall <mpm@selenic.com>
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 8209
diff changeset
     5
# This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 10262
diff changeset
     6
# GNU General Public License version 2 or any later version.
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
8312
b87a50b7125c separate import lines from mercurial and general python modules
Simon Heimberg <simohe@besonet.ch>
parents: 8225
diff changeset
     8
import util
b87a50b7125c separate import lines from mercurial and general python modules
Simon Heimberg <simohe@besonet.ch>
parents: 8225
diff changeset
     9
import heapq
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    10
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    11
def _nonoverlap(d1, d2, d3):
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    12
    "Return list of elements in d1 not in d2 or d3"
8209
a1a5a57efe90 replace util.sort with sorted built-in
Matt Mackall <mpm@selenic.com>
parents: 8152
diff changeset
    13
    return sorted([d for d in d1 if d not in d3 and d not in d2])
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    14
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    15
def _dirname(f):
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    16
    s = f.rfind("/")
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    17
    if s == -1:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    18
        return ""
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    19
    return f[:s]
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    20
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    21
def _dirs(files):
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
    22
    d = set()
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    23
    for f in files:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    24
        f = _dirname(f)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    25
        while f not in d:
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
    26
            d.add(f)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    27
            f = _dirname(f)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    28
    return d
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    29
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    30
def _findlimit(repo, a, b):
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    31
    """Find the earliest revision that's an ancestor of a or b but not both,
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    32
    None if no such revision exists.
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    33
    """
6429
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    34
    # basic idea:
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    35
    # - mark a and b with different sides
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    36
    # - if a parent's children are all on the same side, the parent is
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    37
    #   on that side, otherwise it is on no side
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    38
    # - walk the graph in topological order with the help of a heap;
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    39
    #   - add unseen parents to side map
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    40
    #   - clear side of any parent that has children on different sides
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    41
    #   - track number of interesting revs that might still be on a side
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    42
    #   - track the lowest interesting rev seen
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    43
    #   - quit when interesting revs is zero
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    44
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    45
    cl = repo.changelog
6750
fb42030d79d6 add __len__ and __iter__ methods to repo and revlog
Matt Mackall <mpm@selenic.com>
parents: 6646
diff changeset
    46
    working = len(cl) # pseudo rev for the working directory
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    47
    if a is None:
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    48
        a = working
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    49
    if b is None:
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    50
        b = working
6429
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    51
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    52
    side = {a: -1, b: 1}
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    53
    visit = [-a, -b]
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    54
    heapq.heapify(visit)
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    55
    interesting = len(visit)
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    56
    hascommonancestor = False
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    57
    limit = working
6429
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    58
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    59
    while interesting:
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    60
        r = -heapq.heappop(visit)
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    61
        if r == working:
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    62
            parents = [cl.rev(p) for p in repo.dirstate.parents()]
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    63
        else:
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    64
            parents = cl.parentrevs(r)
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    65
        for p in parents:
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    66
            if p < 0:
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    67
                continue
6429
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    68
            if p not in side:
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    69
                # first time we see p; add it to visit
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    70
                side[p] = side[r]
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    71
                if side[p]:
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    72
                    interesting += 1
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    73
                heapq.heappush(visit, -p)
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    74
            elif side[p] and side[p] != side[r]:
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    75
                # p was interesting but now we know better
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    76
                side[p] = 0
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    77
                interesting -= 1
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    78
                hascommonancestor = True
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    79
        if side[r]:
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    80
            limit = r # lowest rev visited
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    81
            interesting -= 1
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    82
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    83
    if not hascommonancestor:
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
    84
        return None
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    85
    return limit
6429
532ca442b903 symmetricdifference: move back to copies
Matt Mackall <mpm@selenic.com>
parents: 6426
diff changeset
    86
6425
2d9328a2f81f copies: skip directory rename checks when not merging
Matt Mackall <mpm@selenic.com>
parents: 6424
diff changeset
    87
def copies(repo, c1, c2, ca, checkdirs=False):
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    88
    """
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    89
    Find moves and copies between context c1 and c2
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    90
    """
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    91
    # avoid silly behavior for update from empty dir
6430
a6a66e812c34 copies: teach symmetric difference about working revisions
Matt Mackall <mpm@selenic.com>
parents: 6429
diff changeset
    92
    if not c1 or not c2 or c1 == c2:
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    93
        return {}, {}
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    94
6646
9eb274d773d9 copies: teach copies about dirstate.copies
Matt Mackall <mpm@selenic.com>
parents: 6431
diff changeset
    95
    # avoid silly behavior for parent -> working dir
13878
a8d13ee0ce68 misc: replace .parents()[0] with p1()
Matt Mackall <mpm@selenic.com>
parents: 12683
diff changeset
    96
    if c2.node() is None and c1.node() == repo.dirstate.p1():
6646
9eb274d773d9 copies: teach copies about dirstate.copies
Matt Mackall <mpm@selenic.com>
parents: 6431
diff changeset
    97
        return repo.dirstate.copies(), {}
9eb274d773d9 copies: teach copies about dirstate.copies
Matt Mackall <mpm@selenic.com>
parents: 6431
diff changeset
    98
6431
a42d8d3e6ea9 copies: refactor symmetricdifference as _findlimit
Matt Mackall <mpm@selenic.com>
parents: 6430
diff changeset
    99
    limit = _findlimit(repo, c1.rev(), c2.rev())
10179
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
   100
    if limit is None:
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
   101
        # no common ancestor, no copies
83cfa1baf8ad copies: don't report copies with unrelated branch
Patrick Mezard <pmezard@gmail.com>
parents: 9467
diff changeset
   102
        return {}, {}
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   103
    m1 = c1.manifest()
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   104
    m2 = c2.manifest()
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   105
    ma = ca.manifest()
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   106
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   107
    def makectx(f, n):
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   108
        if len(n) != 20: # in a working context?
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   109
            if c1.rev() is None:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   110
                return c1.filectx(f)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   111
            return c2.filectx(f)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   112
        return repo.filectx(f, fileid=n)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   113
9097
431462bd8478 fix memory usage of revlog caches by limiting cache size [issue1639]
Matt Mackall <mpm@selenic.com>
parents: 8527
diff changeset
   114
    ctx = util.lrucachefunc(makectx)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   115
    copy = {}
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   116
    fullcopy = {}
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   117
    diverge = {}
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   118
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   119
    def related(f1, f2, limit):
10874
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   120
        # Walk back to common ancestor to see if the two files originate
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   121
        # from the same file. Since workingfilectx's rev() is None it messes
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   122
        # up the integer comparison logic, hence the pre-step check for
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   123
        # None (f1 and f2 can only be workingfilectx's initially).
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   124
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   125
        if f1 == f2:
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   126
            return f1 # a match
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   127
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   128
        g1, g2 = f1.ancestors(), f2.ancestors()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   129
        try:
10874
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   130
            f1r, f2r = f1.rev(), f2.rev()
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   131
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   132
            if f1r is None:
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   133
                f1 = g1.next()
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   134
            if f2r is None:
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   135
                f2 = g2.next()
4f11978ae45d copies: properly visit file context ancestors on working file contexts
Henrik Stuart <henrik.stuart@edlund.dk>
parents: 10463
diff changeset
   136
14494
1ffeeb91c55d check-code: flag 0/1 used as constant Boolean expression
Martin Geisler <mg@lazybytes.net>
parents: 13878
diff changeset
   137
            while True:
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   138
                f1r, f2r = f1.rev(), f2.rev()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   139
                if f1r > f2r:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   140
                    f1 = g1.next()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   141
                elif f2r > f1r:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   142
                    f2 = g2.next()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   143
                elif f1 == f2:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   144
                    return f1 # a match
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   145
                elif f1r == f2r or f1r < limit or f2r < limit:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   146
                    return False # copy no longer relevant
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   147
        except StopIteration:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   148
            return False
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   149
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   150
    def checkcopies(f, m1, m2):
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   151
        '''check possible copies of f from m1 to m2'''
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   152
        of = None
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   153
        seen = set([f])
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   154
        for oc in ctx(f, m1[f]).ancestors():
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   155
            ocr = oc.rev()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   156
            of = oc.path()
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   157
            if of in seen:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   158
                # check limit late - grab last rename before
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   159
                if ocr < limit:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   160
                    break
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   161
                continue
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   162
            seen.add(of)
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   163
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   164
            fullcopy[f] = of # remember for dir rename detection
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   165
            if of not in m2:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   166
                continue # no match, keep looking
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   167
            if m2[of] == ma.get(of):
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   168
                break # no merge needed, quit early
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   169
            c2 = ctx(of, m2[of])
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   170
            cr = related(oc, c2, ca.rev())
10313
31141fd7c9cc copies: check if revisions are related (bug found with pylint)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 10302
diff changeset
   171
            if cr and (of == f or of == c2.path()): # non-divergent
10262
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   172
                copy[f] = of
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   173
                of = None
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   174
                break
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   175
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   176
        if of in ma:
eb243551cbd8 copies: speed up copy detection
Matt Mackall <mpm@selenic.com>
parents: 10179
diff changeset
   177
            diverge.setdefault(of, []).append(f)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   178
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   179
    repo.ui.debug("  searching for copies back to rev %d\n" % limit)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   180
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   181
    u1 = _nonoverlap(m1, m2, ma)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   182
    u2 = _nonoverlap(m2, m1, ma)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   183
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   184
    if u1:
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   185
        repo.ui.debug("  unmatched files in local:\n   %s\n"
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   186
                      % "\n   ".join(u1))
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   187
    if u2:
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   188
        repo.ui.debug("  unmatched files in other:\n   %s\n"
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   189
                      % "\n   ".join(u2))
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   190
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   191
    for f in u1:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   192
        checkcopies(f, m1, m2)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   193
    for f in u2:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   194
        checkcopies(f, m2, m1)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   195
8152
08e1baf924ca replace set-like dictionaries with real sets
Martin Geisler <mg@lazybytes.net>
parents: 7873
diff changeset
   196
    diverge2 = set()
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   197
    for of, fl in diverge.items():
12683
ada47c38f4e5 copies: don't detect copies as "divergent renames"
Dan Villiom Podlaski Christiansen <danchr@gmail.com>
parents: 10874
diff changeset
   198
        if len(fl) == 1 or of in c2:
ada47c38f4e5 copies: don't detect copies as "divergent renames"
Dan Villiom Podlaski Christiansen <danchr@gmail.com>
parents: 10874
diff changeset
   199
            del diverge[of] # not actually divergent, or not a rename
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   200
        else:
8152
08e1baf924ca replace set-like dictionaries with real sets
Martin Geisler <mg@lazybytes.net>
parents: 7873
diff changeset
   201
            diverge2.update(fl) # reverse map for below
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   202
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   203
    if fullcopy:
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   204
        repo.ui.debug("  all copies found (* = to merge, ! = divergent):\n")
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   205
        for f in fullcopy:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   206
            note = ""
10282
08a0f04b56bd many, many trivial check-code fixups
Matt Mackall <mpm@selenic.com>
parents: 10263
diff changeset
   207
            if f in copy:
08a0f04b56bd many, many trivial check-code fixups
Matt Mackall <mpm@selenic.com>
parents: 10263
diff changeset
   208
                note += "*"
08a0f04b56bd many, many trivial check-code fixups
Matt Mackall <mpm@selenic.com>
parents: 10263
diff changeset
   209
            if f in diverge2:
08a0f04b56bd many, many trivial check-code fixups
Matt Mackall <mpm@selenic.com>
parents: 10263
diff changeset
   210
                note += "!"
8337
0e73e21d81ff copies: don't translate untranslatable string
Martin Geisler <mg@lazybytes.net>
parents: 8312
diff changeset
   211
            repo.ui.debug("   %s -> %s %s\n" % (f, fullcopy[f], note))
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   212
    del diverge2
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   213
6425
2d9328a2f81f copies: skip directory rename checks when not merging
Matt Mackall <mpm@selenic.com>
parents: 6424
diff changeset
   214
    if not fullcopy or not checkdirs:
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   215
        return copy, diverge
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   216
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   217
    repo.ui.debug("  checking for directory renames\n")
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   218
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   219
    # generate a directory move map
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   220
    d1, d2 = _dirs(m1), _dirs(m2)
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
   221
    invalid = set()
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   222
    dirmove = {}
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   223
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   224
    # examine each file copy for a potential directory move, which is
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   225
    # when all the files in a directory are moved to a new directory
7622
4dd7b28003d2 use dict.iteritems() rather than dict.items()
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 6762
diff changeset
   226
    for dst, src in fullcopy.iteritems():
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   227
        dsrc, ddst = _dirname(src), _dirname(dst)
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   228
        if dsrc in invalid:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   229
            # already seen to be uninteresting
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   230
            continue
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   231
        elif dsrc in d1 and ddst in d1:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   232
            # directory wasn't entirely moved locally
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
   233
            invalid.add(dsrc)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   234
        elif dsrc in d2 and ddst in d2:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   235
            # directory wasn't entirely moved remotely
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
   236
            invalid.add(dsrc)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   237
        elif dsrc in dirmove and dirmove[dsrc] != ddst:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   238
            # files from the same directory moved to two different places
8468
b35d11d10646 copies: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8337
diff changeset
   239
            invalid.add(dsrc)
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   240
        else:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   241
            # looks good so far
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   242
            dirmove[dsrc + "/"] = ddst + "/"
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   243
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   244
    for i in invalid:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   245
        if i in dirmove:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   246
            del dirmove[i]
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   247
    del d1, d2, invalid
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   248
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   249
    if not dirmove:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   250
        return copy, diverge
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   251
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   252
    for d in dirmove:
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   253
        repo.ui.debug("  dir %s -> %s\n" % (d, dirmove[d]))
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   254
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   255
    # check unaccounted nonoverlapping files against directory moves
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   256
    for f in u1 + u2:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   257
        if f not in fullcopy:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   258
            for d in dirmove:
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   259
                if f.startswith(d):
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   260
                    # new file added in a directory that was moved, move it
6425
2d9328a2f81f copies: skip directory rename checks when not merging
Matt Mackall <mpm@selenic.com>
parents: 6424
diff changeset
   261
                    df = dirmove[d] + f[len(d):]
6426
e2c49ef2dd6e copies: don't double-detect items in the directory copy check
Matt Mackall <mpm@selenic.com>
parents: 6425
diff changeset
   262
                    if df not in copy:
e2c49ef2dd6e copies: don't double-detect items in the directory copy check
Matt Mackall <mpm@selenic.com>
parents: 6425
diff changeset
   263
                        copy[f] = df
9467
4c041f1ee1b4 do not attempt to translate ui.debug output
Martin Geisler <mg@lazybytes.net>
parents: 9102
diff changeset
   264
                        repo.ui.debug("  file %s -> %s\n" % (f, copy[f]))
6274
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   265
                    break
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   266
f3f383efbeae copies: move findcopies code to its own module
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   267
    return copy, diverge