1 # copies.py - copy detection for Mercurial

     2 #

     3 # Copyright 2008 Matt Mackall <mpm@selenic.com>

     4 #

     5 # This software may be used and distributed according to the terms of the

     6 # GNU General Public License version 2 or any later version.

     7 

     8 import util

     9 import heapq

    10 

    11 def _nonoverlap(d1, d2, d3):

    12     "Return list of elements in d1 not in d2 or d3"

    13     return sorted([d for d in d1 if d not in d3 and d not in d2])

    14 

    15 def _dirname(f):

    16     s = f.rfind("/")

    17     if s == -1:

    18         return ""

    19     return f[:s]

    20 

    21 def _dirs(files):

    22     d = set()

    23     for f in files:

    24         f = _dirname(f)

    25         while f not in d:

    26             d.add(f)

    27             f = _dirname(f)

    28     return d

    29 

    30 def _findlimit(repo, a, b):

    31     """Find the earliest revision that's an ancestor of a or b but not both,

    32     None if no such revision exists.

    33     """

    34     # basic idea:

    35     # - mark a and b with different sides

    36     # - if a parent's children are all on the same side, the parent is

    37     #   on that side, otherwise it is on no side

    38     # - walk the graph in topological order with the help of a heap;

    39     #   - add unseen parents to side map

    40     #   - clear side of any parent that has children on different sides

    41     #   - track number of interesting revs that might still be on a side

    42     #   - track the lowest interesting rev seen

    43     #   - quit when interesting revs is zero

    44 

    45     cl = repo.changelog

    46     working = len(cl) # pseudo rev for the working directory

    47     if a is None:

    48         a = working

    49     if b is None:

    50         b = working

    51 

    52     side = {a: -1, b: 1}

    53     visit = [-a, -b]

    54     heapq.heapify(visit)

    55     interesting = len(visit)

    56     hascommonancestor = False

    57     limit = working

    58 

    59     while interesting:

    60         r = -heapq.heappop(visit)

    61         if r == working:

    62             parents = [cl.rev(p) for p in repo.dirstate.parents()]

    63         else:

    64             parents = cl.parentrevs(r)

    65         for p in parents:

    66             if p < 0:

    67                 continue

    68             if p not in side:

    69                 # first time we see p; add it to visit

    70                 side[p] = side[r]

    71                 if side[p]:

    72                     interesting += 1

    73                 heapq.heappush(visit, -p)

    74             elif side[p] and side[p] != side[r]:

    75                 # p was interesting but now we know better

    76                 side[p] = 0

    77                 interesting -= 1

    78                 hascommonancestor = True

    79         if side[r]:

    80             limit = r # lowest rev visited

    81             interesting -= 1

    82 

    83     if not hascommonancestor:

    84         return None

    85     return limit

    86 

    87 def copies(repo, c1, c2, ca, checkdirs=False):

    88     """

    89     Find moves and copies between context c1 and c2

    90     """

    91     # avoid silly behavior for update from empty dir

    92     if not c1 or not c2 or c1 == c2:

    93         return {}, {}

    94 

    95     # avoid silly behavior for parent -> working dir

    96     if c2.node() is None and c1.node() == repo.dirstate.parents()[0]:

    97         return repo.dirstate.copies(), {}

    98 

    99     limit = _findlimit(repo, c1.rev(), c2.rev())

   100     if limit is None:

   101         # no common ancestor, no copies

   102         return {}, {}

   103     m1 = c1.manifest()

   104     m2 = c2.manifest()

   105     ma = ca.manifest()

   106 

   107     def makectx(f, n):

   108         if len(n) != 20: # in a working context?

   109             if c1.rev() is None:

   110                 return c1.filectx(f)

   111             return c2.filectx(f)

   112         return repo.filectx(f, fileid=n)

   113 

   114     ctx = util.lrucachefunc(makectx)

   115     copy = {}

   116     fullcopy = {}

   117     diverge = {}

   118 

   119     def related(f1, f2, limit):

   120         # Walk back to common ancestor to see if the two files originate

   121         # from the same file. Since workingfilectx's rev() is None it messes

   122         # up the integer comparison logic, hence the pre-step check for

   123         # None (f1 and f2 can only be workingfilectx's initially).

   124 

   125         if f1 == f2:

   126             return f1 # a match

   127 

   128         g1, g2 = f1.ancestors(), f2.ancestors()

   129         try:

   130             f1r, f2r = f1.rev(), f2.rev()

   131 

   132             if f1r is None:

   133                 f1 = g1.next()

   134             if f2r is None:

   135                 f2 = g2.next()

   136 

   137             while 1:

   138                 f1r, f2r = f1.rev(), f2.rev()

   139                 if f1r > f2r:

   140                     f1 = g1.next()

   141                 elif f2r > f1r:

   142                     f2 = g2.next()

   143                 elif f1 == f2:

   144                     return f1 # a match

   145                 elif f1r == f2r or f1r < limit or f2r < limit:

   146                     return False # copy no longer relevant

   147         except StopIteration:

   148             return False

   149 

   150     def checkcopies(f, m1, m2):

   151         '''check possible copies of f from m1 to m2'''

   152         of = None

   153         seen = set([f])

   154         for oc in ctx(f, m1[f]).ancestors():

   155             ocr = oc.rev()

   156             of = oc.path()

   157             if of in seen:

   158                 # check limit late - grab last rename before

   159                 if ocr < limit:

   160                     break

   161                 continue

   162             seen.add(of)

   163 

   164             fullcopy[f] = of # remember for dir rename detection

   165             if of not in m2:

   166                 continue # no match, keep looking

   167             if m2[of] == ma.get(of):

   168                 break # no merge needed, quit early

   169             c2 = ctx(of, m2[of])

   170             cr = related(oc, c2, ca.rev())

   171             if cr and (of == f or of == c2.path()): # non-divergent

   172                 copy[f] = of

   173                 of = None

   174                 break

   175 

   176         if of in ma:

   177             diverge.setdefault(of, []).append(f)

   178 

   179     repo.ui.debug("  searching for copies back to rev %d\n" % limit)

   180 

   181     u1 = _nonoverlap(m1, m2, ma)

   182     u2 = _nonoverlap(m2, m1, ma)

   183 

   184     if u1:

   185         repo.ui.debug("  unmatched files in local:\n   %s\n"

   186                       % "\n   ".join(u1))

   187     if u2:

   188         repo.ui.debug("  unmatched files in other:\n   %s\n"

   189                       % "\n   ".join(u2))

   190 

   191     for f in u1:

   192         checkcopies(f, m1, m2)

   193     for f in u2:

   194         checkcopies(f, m2, m1)

   195 

   196     diverge2 = set()

   197     for of, fl in diverge.items():

   198         if len(fl) == 1 or of in c2:

   199             del diverge[of] # not actually divergent, or not a rename

   200         else:

   201             diverge2.update(fl) # reverse map for below

   202 

   203     if fullcopy:

   204         repo.ui.debug("  all copies found (* = to merge, ! = divergent):\n")

   205         for f in fullcopy:

   206             note = ""

   207             if f in copy:

   208                 note += "*"

   209             if f in diverge2:

   210                 note += "!"

   211             repo.ui.debug("   %s -> %s %s\n" % (f, fullcopy[f], note))

   212     del diverge2

   213 

   214     if not fullcopy or not checkdirs:

   215         return copy, diverge

   216 

   217     repo.ui.debug("  checking for directory renames\n")

   218 

   219     # generate a directory move map

   220     d1, d2 = _dirs(m1), _dirs(m2)

   221     invalid = set()

   222     dirmove = {}

   223 

   224     # examine each file copy for a potential directory move, which is

   225     # when all the files in a directory are moved to a new directory

   226     for dst, src in fullcopy.iteritems():

   227         dsrc, ddst = _dirname(src), _dirname(dst)

   228         if dsrc in invalid:

   229             # already seen to be uninteresting

   230             continue

   231         elif dsrc in d1 and ddst in d1:

   232             # directory wasn't entirely moved locally

   233             invalid.add(dsrc)

   234         elif dsrc in d2 and ddst in d2:

   235             # directory wasn't entirely moved remotely

   236             invalid.add(dsrc)

   237         elif dsrc in dirmove and dirmove[dsrc] != ddst:

   238             # files from the same directory moved to two different places

   239             invalid.add(dsrc)

   240         else:

   241             # looks good so far

   242             dirmove[dsrc + "/"] = ddst + "/"

   243 

   244     for i in invalid:

   245         if i in dirmove:

   246             del dirmove[i]

   247     del d1, d2, invalid

   248 

   249     if not dirmove:

   250         return copy, diverge

   251 

   252     for d in dirmove:

   253         repo.ui.debug("  dir %s -> %s\n" % (d, dirmove[d]))

   254 

   255     # check unaccounted nonoverlapping files against directory moves

   256     for f in u1 + u2:

   257         if f not in fullcopy:

   258             for d in dirmove:

   259                 if f.startswith(d):

   260                     # new file added in a directory that was moved, move it

   261                     df = dirmove[d] + f[len(d):]

   262                     if df not in copy:

   263                         copy[f] = df

   264                         repo.ui.debug("  file %s -> %s\n" % (f, copy[f]))

   265                     break

   266 

   267     return copy, diverge