comparison mercurial/copies.py @ 30195:88626de195f8

copies: make _checkcopies handle simple renames in a rotated DAG

This introduces a distinction between "merge base" and
"topological common ancestor". During a regular merge, these two are
identical. Graft, however, performs a merge in a rotated DAG, where the
merge base will not be a common ancestor at all in the
original DAG.

To correctly find copies in case of a graft, we need to take both the
merge base and the topological CA into account, and track any renames
between them in reverse. Fortunately we can detect this in advance,
see comment in the code about "backwards".

This patch only supports finding non-divergent renames contained entirely
between the merge base and the topological CA. Further patches are coming
to support more complex cases.

(Pierre-Yves David was involved in the cleanup of this patch.)

30194:8c69c52ced98

    u1r, u2r = _computenonoverlap(repo, c1, c2, addedinm1, addedinm2)
    u1u, u2u = u1r, u2r
    bothnew = sorted(addedinm1 & addedinm2)

    for f in u1u:
        _checkcopies(c1, f, m1, m2, base, limit, data1)

    for f in u2u:
        _checkcopies(c2, f, m2, m1, base, limit, data2)

    copy = dict(data1['copy'].items() + data2['copy'].items())
    fullcopy = dict(data1['fullcopy'].items() + data2['fullcopy'].items())

    renamedelete = {}

    bothdata = {'copy': {},
                'fullcopy': {},
                'diverge': bothdiverge,
               }
    for f in bothnew:
        _checkcopies(c1, f, m1, m2, base, limit, bothdata)
        _checkcopies(c2, f, m2, m1, base, limit, bothdata)
    for of, fl in bothdiverge.items():
        if len(fl) == 2 and fl[0] == fl[1]:
            copy[fl[0]] = of # not actually divergent, just matching renames

    if fullcopy and repo.ui.debugflag:

            elif f1r == f2r or f1r < limit or f2r < limit:
                return False # copy no longer relevant
    except StopIteration:
        return False

def _checkcopies(ctx, f, m1, m2, base, limit, data):
    """
    check possible copies of f from m1 to m2

    ctx = starting context for f in m1
    f = the filename to check (as in m1)
    m1 = the source manifest
    m2 = the destination manifest
    base = the changectx used as a merge base
    limit = the rev number to not search beyond
    data = dictionary of dictionary to store copy data. (see mergecopies)

    note: limit is only an optimization, and there is no guarantee that
    irrelevant revisions will not be limited
    there is no easy way to make this algorithm stop in a guaranteed way
    once it "goes behind a certain revision".
    """

    mb = base.manifest()
    getfctx = _makegetfctx(ctx)

    of = None
    seen = set([f])
    for oc in getfctx(f, m1[f]).ancestors():

            if ocr < limit:
                break
            continue
        seen.add(of)

        data['fullcopy'][f] = of # remember for dir rename detection
        if of not in m2:
            continue # no match, keep looking
        if m2[of] == mb.get(of):
            return # no merge needed, quit early
        c2 = getfctx(of, m2[of])
        # c2 might be a plain new file on added on destination side that is
        # unrelated to the droids we are looking for.
        cr = _related(oc, c2, base.rev())
        if cr and (of == f or of == c2.path()): # non-divergent
            if of in mb:
                data['copy'][f] = of
            return

    if of in mb:
        data['diverge'].setdefault(of, []).append(f)

30195:88626de195f8

    u1r, u2r = _computenonoverlap(repo, c1, c2, addedinm1, addedinm2)
    u1u, u2u = u1r, u2r
    bothnew = sorted(addedinm1 & addedinm2)

    for f in u1u:
        _checkcopies(c1, f, m1, m2, base, tca, limit, data1)

    for f in u2u:
        _checkcopies(c2, f, m2, m1, base, tca, limit, data2)

    copy = dict(data1['copy'].items() + data2['copy'].items())
    fullcopy = dict(data1['fullcopy'].items() + data2['fullcopy'].items())

    renamedelete = {}

    bothdata = {'copy': {},
                'fullcopy': {},
                'diverge': bothdiverge,
               }
    for f in bothnew:
        _checkcopies(c1, f, m1, m2, base, tca, limit, bothdata)
        _checkcopies(c2, f, m2, m1, base, tca, limit, bothdata)
    for of, fl in bothdiverge.items():
        if len(fl) == 2 and fl[0] == fl[1]:
            copy[fl[0]] = of # not actually divergent, just matching renames

    if fullcopy and repo.ui.debugflag:

            elif f1r == f2r or f1r < limit or f2r < limit:
                return False # copy no longer relevant
    except StopIteration:
        return False

def _checkcopies(ctx, f, m1, m2, base, tca, limit, data):
    """
    check possible copies of f from m1 to m2

    ctx = starting context for f in m1
    f = the filename to check (as in m1)
    m1 = the source manifest
    m2 = the destination manifest
    base = the changectx used as a merge base
    tca = topological common ancestor for graft-like scenarios
    limit = the rev number to not search beyond
    data = dictionary of dictionary to store copy data. (see mergecopies)

    note: limit is only an optimization, and there is no guarantee that
    irrelevant revisions will not be limited
    there is no easy way to make this algorithm stop in a guaranteed way
    once it "goes behind a certain revision".
    """

    mb = base.manifest()
    # Might be true if this call is about finding backward renames,
    # This happens in the case of grafts because the DAG is then rotated.
    # If the file exists in both the base and the source, we are not looking
    # for a rename on the source side, but on the part of the DAG that is
    # traversed backwards.
    #
    # In the case there is both backward and forward renames (before and after
    # the base) this is more complicated as we must detect a divergence. This
    # is currently broken and hopefully some later code update will make that
    # work (we use 'backwards = False' in that case)
    backwards = base != tca and f in mb
    getfctx = _makegetfctx(ctx)

    of = None
    seen = set([f])
    for oc in getfctx(f, m1[f]).ancestors():

            if ocr < limit:
                break
            continue
        seen.add(of)

        # remember for dir rename detection
        if backwards:
            data['fullcopy'][of] = f # grafting backwards through renames
        else:
            data['fullcopy'][f] = of
        if of not in m2:
            continue # no match, keep looking
        if m2[of] == mb.get(of):
            return # no merge needed, quit early
        c2 = getfctx(of, m2[of])
        # c2 might be a plain new file on added on destination side that is
        # unrelated to the droids we are looking for.
        cr = _related(oc, c2, tca.rev())
        if cr and (of == f or of == c2.path()): # non-divergent
            if backwards:
                data['copy'][of] = f
            elif of in mb:
                data['copy'][f] = of
            return

    if of in mb:
        data['diverge'].setdefault(of, []).append(f)