# synthrepo.py - repo synthesis

#

# Copyright 2012 Facebook

#

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

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

'''synthesize structurally interesting change history

This extension is useful for creating a repository with properties

that are statistically similar to an existing repository. During

analysis, a simple probability table is constructed from the history

of an existing repository.  During synthesis, these properties are

reconstructed.

Properties that are analyzed and synthesized include the following:

- Lines added or removed when an existing file is modified

- Number and sizes of files added

- Number of files removed

- Line lengths

- Topological distance to parent changeset(s)

- Probability of a commit being a merge

- Probability of a newly added file being added to a new directory

- Interarrival time, and time zone, of commits

A few obvious properties that are not currently handled realistically:

- Merges are treated as regular commits with two parents, which is not

  realistic

- Modifications are not treated as operations on hunks of lines, but

  as insertions and deletions of randomly chosen single lines

- Committer ID (always random)

- Executability of files

- Symlinks and binary files are ignored

'''

import bisect, collections, json, os, random, time, sys

from mercurial import cmdutil, context, patch, scmutil, util, hg

from mercurial.i18n import _

from mercurial.node import nullrev, nullid

testedwith = 'internal'

cmdtable = {}

command = cmdutil.command(cmdtable)

newfile = set(('new fi', 'rename', 'copy f', 'copy t'))

def zerodict():

    return collections.defaultdict(lambda: 0)

def roundto(x, k):

    if x > k * 2:

        return int(round(x / float(k)) * k)

    return int(round(x))

def parsegitdiff(lines):

    filename, mar, lineadd, lineremove = None, None, zerodict(), 0

    binary = False

    for line in lines:

        start = line[:6]

        if start == 'diff -':

            if filename:

                yield filename, mar, lineadd, lineremove, binary

            mar, lineadd, lineremove, binary = 'm', zerodict(), 0, False

            filename = patch.gitre.match(line).group(1)

        elif start in newfile:

            mar = 'a'

        elif start == 'GIT bi':

            binary = True

        elif start == 'delete':

            mar = 'r'

        elif start:

            s = start[0]

            if s == '-' and not line.startswith('--- '):

                lineremove += 1

            elif s == '+' and not line.startswith('+++ '):

                lineadd[roundto(len(line) - 1, 5)] += 1

    if filename:

        yield filename, mar, lineadd, lineremove, binary

@command('analyze',

         [('o', 'output', [], _('write output to given file'), _('FILE')),

          ('r', 'rev', [], _('analyze specified revisions'), _('REV'))],

         _('hg analyze'))

def analyze(ui, repo, *revs, **opts):

    '''create a simple model of a repository to use for later synthesis

    This command examines every changeset in the given range (or all

    of history if none are specified) and creates a simple statistical

    model of the history of the repository.

    The model is written out to a JSON file, and can be used by

    :hg:`synthesize` to create or augment a repository with synthetic

    commits that have a structure that is statistically similar to the

    analyzed repository.

    '''

    revs = list(revs)

    revs.extend(opts['rev'])

    if not revs:

        revs = [':']

    output = opts['output']

    if not output:

        output = os.path.basename(repo.root) + '.json'

    if output == '-':

        fp = sys.stdout

    else:

        fp = open(output, 'w')

    revs = scmutil.revrange(repo, revs)

    revs.sort()

    lineschanged = zerodict()

    children = zerodict()

    p1distance = zerodict()

    p2distance = zerodict()

    linesinfilesadded = zerodict()

    fileschanged = zerodict()

    filesadded = zerodict()

    filesremoved = zerodict()

    linelengths = zerodict()

    interarrival = zerodict()

    parents = zerodict()

    dirsadded = zerodict()

    tzoffset = zerodict()

    progress = ui.progress

    _analyzing = _('analyzing')

    _changesets = _('changesets')

    _total = len(revs)

    for i, rev in enumerate(revs):

        progress(_analyzing, i, unit=_changesets, total=_total)

        ctx = repo[rev]

        pl = ctx.parents()

        pctx = pl[0]

        prev = pctx.rev()

        children[prev] += 1

        p1distance[rev - prev] += 1

        parents[len(pl)] += 1

        tzoffset[ctx.date()[1]] += 1

        if len(pl) > 1:

            p2distance[rev - pl[1].rev()] += 1

        if prev == rev - 1:

            lastctx = pctx

        else:

            lastctx = repo[rev - 1]

        if lastctx.rev() != nullrev:

            interarrival[roundto(ctx.date()[0] - lastctx.date()[0], 300)] += 1

        diff = sum((d.splitlines()

                    for d in ctx.diff(pctx, opts={'git': True})), [])

        fileadds, diradds, fileremoves, filechanges = 0, 0, 0, 0

        for filename, mar, lineadd, lineremove, binary in parsegitdiff(diff):

            if binary:

                continue

            added = sum(lineadd.itervalues(), 0)

            if mar == 'm':

                if added and lineremove:

                    lineschanged[roundto(added, 5), roundto(lineremove, 5)] += 1

                    filechanges += 1

            elif mar == 'a':

                fileadds += 1

                if '/' in filename:

                    filedir = filename.rsplit('/', 1)[0]

                    if filedir not in pctx.dirs():

                        diradds += 1

                linesinfilesadded[roundto(added, 5)] += 1

            elif mar == 'r':

                fileremoves += 1

            for length, count in lineadd.iteritems():

                linelengths[length] += count

        fileschanged[filechanges] += 1

        filesadded[fileadds] += 1

        dirsadded[diradds] += 1

        filesremoved[fileremoves] += 1

    invchildren = zerodict()

    for rev, count in children.iteritems():

        invchildren[count] += 1

    if output != '-':

        ui.status(_('writing output to %s\n') % output)

    def pronk(d):

        return sorted(d.iteritems(), key=lambda x: x[1], reverse=True)

    json.dump({'revs': len(revs),

               'lineschanged': pronk(lineschanged),

               'children': pronk(invchildren),

               'fileschanged': pronk(fileschanged),

               'filesadded': pronk(filesadded),

               'linesinfilesadded': pronk(linesinfilesadded),

               'dirsadded': pronk(dirsadded),

               'filesremoved': pronk(filesremoved),

               'linelengths': pronk(linelengths),

               'parents': pronk(parents),

               'p1distance': pronk(p1distance),

               'p2distance': pronk(p2distance),

               'interarrival': pronk(interarrival),

               'tzoffset': pronk(tzoffset),

               },

              fp)

    fp.close()

@command('synthesize',

         [('c', 'count', 0, _('create given number of commits'), _('COUNT')),

          ('', 'dict', '', _('path to a dictionary of words'), _('FILE'))],

         _('hg synthesize [OPTION].. DESCFILE'))

def synthesize(ui, repo, descpath, **opts):

    '''synthesize commits based on a model of an existing repository

    The model must have been generated by :hg:`analyze`. Commits will

    be generated randomly according to the probabilities described in

    the model.

    When synthesizing new content, commit descriptions, and user

    names, words will be chosen randomly from a dictionary that is

    presumed to contain one word per line. Use --dict to specify the

    path to an alternate dictionary to use.

    '''

    try:

        fp = hg.openpath(ui, descpath)

    except Exception, err:

        raise util.Abort('%s: %s' % (descpath, err[0].strerror))

    desc = json.load(fp)

    fp.close()

    def cdf(l):

        if not l:

            return [], []

        vals, probs = zip(*sorted(l, key=lambda x: x[1], reverse=True))

        t = float(sum(probs, 0))

        s, cdfs = 0, []

        for v in probs:

            s += v

            cdfs.append(s / t)

        return vals, cdfs

    lineschanged = cdf(desc['lineschanged'])

    fileschanged = cdf(desc['fileschanged'])

    filesadded = cdf(desc['filesadded'])

    dirsadded = cdf(desc['dirsadded'])

    filesremoved = cdf(desc['filesremoved'])

    linelengths = cdf(desc['linelengths'])

    parents = cdf(desc['parents'])

    p1distance = cdf(desc['p1distance'])

    p2distance = cdf(desc['p2distance'])

    interarrival = cdf(desc['interarrival'])

    linesinfilesadded = cdf(desc['linesinfilesadded'])

    tzoffset = cdf(desc['tzoffset'])

    dictfile = opts.get('dict') or '/usr/share/dict/words'

    try:

        fp = open(dictfile, 'rU')

    except IOError, err:

        raise util.Abort('%s: %s' % (dictfile, err.strerror))

    words = fp.read().splitlines()

    fp.close()

    def pick(cdf):

        return cdf[0][bisect.bisect_left(cdf[1], random.random())]

    def makeline(minimum=0):

        total = max(minimum, pick(linelengths))

        c, l = 0, []

        while c < total:

            w = random.choice(words)

            c += len(w) + 1

            l.append(w)

        return ' '.join(l)

    wlock = repo.wlock()

    lock = repo.lock()

    nevertouch = set(('.hgsub', '.hgignore', '.hgtags'))

    progress = ui.progress

    _synthesizing = _('synthesizing')

    _changesets = _('changesets')

    count = int(opts['count'])

    heads = set(map(repo.changelog.rev, repo.heads()))

    for i in xrange(count):

        progress(_synthesizing, i, unit=_changesets, total=count)

        node = repo.changelog.node

        revs = len(repo)

        def pickhead(heads, distance):

            if heads:

                lheads = sorted(heads)

                rev = revs - min(pick(distance), revs)

                if rev < lheads[-1]:

                    rev = lheads[bisect.bisect_left(lheads, rev)]

                else:

                    rev = lheads[-1]

                return rev, node(rev)

            return nullrev, nullid

        r1 = revs - min(pick(p1distance), revs)

        p1 = node(r1)

        # the number of heads will grow without bound if we use a pure

        # model, so artificially constrain their proliferation

        if pick(parents) == 2 or len(heads) > random.randint(1, 20):

            r2, p2 = pickhead(heads.difference([r1]), p2distance)

        else:

            r2, p2 = nullrev, nullid

        pl = [p1, p2]

        pctx = repo[r1]

        mf = pctx.manifest()

        mfk = mf.keys()

        changes = {}

        if mfk:

            for __ in xrange(pick(fileschanged)):

                for __ in xrange(10):

                    fctx = pctx.filectx(random.choice(mfk))

                    path = fctx.path()

                    if not (path in nevertouch or fctx.isbinary() or

                            'l' in fctx.flags()):

                        break

                lines = fctx.data().splitlines()

                add, remove = pick(lineschanged)

                for __ in xrange(remove):

                    if not lines:

                        break

                    del lines[random.randrange(0, len(lines))]

                for __ in xrange(add):

                    lines.insert(random.randint(0, len(lines)), makeline())

                path = fctx.path()

                changes[path] = context.memfilectx(repo, path,

                                                   '\n'.join(lines) + '\n')

            for __ in xrange(pick(filesremoved)):

                path = random.choice(mfk)

                for __ in xrange(10):

                    path = random.choice(mfk)

                    if path not in changes:

                        changes[path] = None

                        break

        if filesadded:

            dirs = list(pctx.dirs())

            dirs.append('')

        for __ in xrange(pick(filesadded)):

            path = [random.choice(dirs)]

            if pick(dirsadded):

                path.append(random.choice(words))

            path.append(random.choice(words))

            path = '/'.join(filter(None, path))

            data = '\n'.join(makeline()

                             for __ in xrange(pick(linesinfilesadded))) + '\n'

            changes[path] = context.memfilectx(repo, path, data)

        def filectxfn(repo, memctx, path):

            data = changes[path]

            if data is None:

                raise IOError

            return data

        if not changes:

            continue

        if revs:

            date = repo['tip'].date()[0] + pick(interarrival)

        else:

            date = time.time() - (86400 * count)

        user = random.choice(words) + '@' + random.choice(words)

        mc = context.memctx(repo, pl, makeline(minimum=2),

                            sorted(changes.iterkeys()),

                            filectxfn, user, '%d %d' % (date, pick(tzoffset)))

        newnode = mc.commit()

        heads.add(repo.changelog.rev(newnode))

        heads.discard(r1)

        heads.discard(r2)

    lock.release()

    wlock.release()