import binascii

import getopt

import math

import os

import random

import sys

import time

from mercurial.node import nullrev

from mercurial import (

    ancestor,

    debugcommands,

    hg,

    pycompat,

    ui as uimod,

    util,

)

if pycompat.ispy3:

    long = int

    xrange = range

def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):

    """nodes: total number of nodes in the graph

    rootprob: probability that a new node (not 0) will be a root

    mergeprob: probability that, excluding a root a node will be a merge

    prevprob: probability that p1 will be the previous node

    return value is a graph represented as an adjacency list.

    """

    graph = [None] * nodes

    for i in xrange(nodes):

        if i == 0 or rng.random() < rootprob:

            graph[i] = [nullrev]

        elif i == 1:

            graph[i] = [0]

        elif rng.random() < mergeprob:

            if i == 2 or rng.random() < prevprob:

                # p1 is prev

                p1 = i - 1

            else:

                p1 = rng.randrange(i - 1)

            p2 = rng.choice(list(range(0, p1)) + list(range(p1 + 1, i)))

            graph[i] = [p1, p2]

        elif rng.random() < prevprob:

            graph[i] = [i - 1]

        else:

            graph[i] = [rng.randrange(i - 1)]

    return graph

def buildancestorsets(graph):

    ancs = [None] * len(graph)

    for i in xrange(len(graph)):

        ancs[i] = {i}

        if graph[i] == [nullrev]:

            continue

        for p in graph[i]:

            ancs[i].update(ancs[p])

    return ancs

    def __init__(self, ancs, bases):

        self.ancs = ancs

        self.bases = set(bases)

    def addbases(self, newbases):

        self.bases.update(newbases)

    def removeancestorsfrom(self, revs):

        for base in self.bases:

            if base != nullrev:

                revs.difference_update(self.ancs[base])

        revs.discard(nullrev)

    def missingancestors(self, revs):

        res = set()

        for rev in revs:

            if rev != nullrev:

                res.update(self.ancs[rev])

        for base in self.bases:

            if base != nullrev:

                res.difference_update(self.ancs[base])

        return sorted(res)

def test_missingancestors(seed, rng):

    # empirically observed to take around 1 second

    graphcount = 100

    testcount = 10

    inccount = 10

    nerrs = [0]

    # the default mu and sigma give us a nice distribution of mostly

    # single-digit counts (including 0) with some higher ones

    def lognormrandom(mu, sigma):

        return int(math.floor(rng.lognormvariate(mu, sigma)))

    def samplerevs(nodes, mu=1.1, sigma=0.8):

        count = min(lognormrandom(mu, sigma), len(nodes))

        return rng.sample(nodes, count)

    def err(seed, graph, bases, seq, output, expected):

        if nerrs[0] == 0:

            print('seed:', hex(seed)[:-1], file=sys.stderr)

        if gerrs[0] == 0:

            print('graph:', graph, file=sys.stderr)

        print('* bases:', bases, file=sys.stderr)

        print('* seq: ', seq, file=sys.stderr)

        print('*  output:  ', output, file=sys.stderr)

        print('*  expected:', expected, file=sys.stderr)

        nerrs[0] += 1

        gerrs[0] += 1

    for g in xrange(graphcount):

        graph = buildgraph(rng)

        ancs = buildancestorsets(graph)

        gerrs = [0]

        for _ in xrange(testcount):

            # start from nullrev to include it as a possibility

            graphnodes = range(nullrev, len(graph))

            bases = samplerevs(graphnodes)

            # fast algorithm

            inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases)

            # reference slow algorithm

            naiveinc = naiveincrementalmissingancestors(ancs, bases)

            seq = []

            for _ in xrange(inccount):

                if rng.random() < 0.2:

                    newbases = samplerevs(graphnodes)

                    seq.append(('addbases', newbases))

                    inc.addbases(newbases)

                    naiveinc.addbases(newbases)

                if rng.random() < 0.4:

                    # larger set so that there are more revs to remove from

                    revs = samplerevs(graphnodes, mu=1.5)

                    seq.append(('removeancestorsfrom', revs))

                    hrevs = set(revs)

                    rrevs = set(revs)

                    inc.removeancestorsfrom(hrevs)

                    naiveinc.removeancestorsfrom(rrevs)

                    if hrevs != rrevs:

                        err(

                            seed,

                            graph,

                            bases,

                            seq,

                            sorted(hrevs),

                            sorted(rrevs),

                        )

                else:

                    revs = samplerevs(graphnodes)

                    seq.append(('missingancestors', revs))

                    h = inc.missingancestors(revs)

                    r = naiveinc.missingancestors(revs)

                    if h != r:

                        err(seed, graph, bases, seq, h, r)

# graph is a dict of child->parent adjacency lists for this graph:

# o  13

# |

# | o  12

# | |

# | | o    11

# | | |\

# | | | | o  10

# | | | | |

# | o---+ |  9

# | | | | |

# o | | | |  8

#  / / / /

# | | o |  7

# | | | |

# o---+ |  6

#  / / /

# | | o  5

# | |/

# | o  4

# | |

# o |  3

# | |

# | o  2

# |/

# o  1

# |

# o  0

graph = {

    0: [-1, -1],

    1: [0, -1],

    2: [1, -1],

    3: [1, -1],

    4: [2, -1],

    5: [4, -1],

    6: [4, -1],

    7: [4, -1],

    8: [-1, -1],

    9: [6, 7],

    10: [5, -1],

    11: [3, 7],

    12: [9, -1],

    13: [8, -1],

}

def test_missingancestors_explicit():

    """A few explicit cases, easier to check for catching errors in refactors.

    The bigger graph at the end has been produced by the random generator

    above, and we have some evidence that the other tests don't cover it.

    """

    for i, (bases, revs) in enumerate(

        (

            ({1, 2, 3, 4, 7}, set(xrange(10))),

            ({10}, set({11, 12, 13, 14})),

            ({7}, set({1, 2, 3, 4, 5})),

        )

    ):

        print("%% removeancestorsfrom(), example %d" % (i + 1))

        missanc = ancestor.incrementalmissingancestors(graph.get, bases)

        missanc.removeancestorsfrom(revs)

        print("remaining (sorted): %s" % sorted(list(revs)))

    for i, (bases, revs) in enumerate(

        (

            ({10}, {11}),

            ({11}, {10}),

            ({7}, {9, 11}),

        )

    ):

        print("%% missingancestors(), example %d" % (i + 1))

        missanc = ancestor.incrementalmissingancestors(graph.get, bases)

        print("return %s" % missanc.missingancestors(revs))

    print("% removeancestorsfrom(), bigger graph")

    vecgraph = [

        [-1, -1],

        [0, -1],

        [1, 0],

        [2, 1],

        [3, -1],

        [4, -1],

        [5, 1],

        [2, -1],

        [7, -1],

        [8, -1],

        [9, -1],

        [10, 1],

        [3, -1],

        [12, -1],

        [13, -1],

        [14, -1],

        [4, -1],

        [16, -1],

        [17, -1],

        [18, -1],

        [19, 11],

        [20, -1],

        [21, -1],

        [22, -1],

        [23, -1],

        [2, -1],

        [3, -1],

        [26, 24],

        [27, -1],

        [28, -1],

        [12, -1],

        [1, -1],

        [1, 9],

        [32, -1],

        [33, -1],

        [34, 31],

        [35, -1],

        [36, 26],

        [37, -1],

        [38, -1],

        [39, -1],

        [40, -1],

        [41, -1],

        [42, 26],

        [0, -1],

        [44, -1],

        [45, 4],

        [40, -1],

        [47, -1],

        [36, 0],

        [49, -1],

        [-1, -1],

        [51, -1],

        [52, -1],

        [53, -1],

        [14, -1],

        [55, -1],

        [15, -1],

        [23, -1],

        [58, -1],

        [59, -1],

        [2, -1],

        [61, 59],

        [62, -1],

        [63, -1],

        [-1, -1],

        [65, -1],

        [66, -1],

        [67, -1],

        [68, -1],

        [37, 28],

        [69, 25],

        [71, -1],

        [72, -1],

        [50, 2],

        [74, -1],

        [12, -1],

        [18, -1],

        [77, -1],

        [78, -1],

        [79, -1],

        [43, 33],

        [81, -1],

        [82, -1],

        [83, -1],

        [84, 45],

        [85, -1],

        [86, -1],

        [-1, -1],

        [88, -1],

        [-1, -1],

        [76, 83],

        [44, -1],

        [92, -1],

        [93, -1],

        [9, -1],

        [95, 67],

        [96, -1],

        [97, -1],

        [-1, -1],

    ]

    problem_rev = 28

    problem_base = 70

    # problem_rev is a parent of problem_base, but a faulty implementation

    # could forget to remove it.

    bases = {60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6}

    if problem_rev not in vecgraph[problem_base] or problem_base not in bases:

        print("Conditions have changed")

    missanc = ancestor.incrementalmissingancestors(vecgraph.__getitem__, bases)

    revs = {4, 12, 41, 28, 68, 38, 1, 30, 56, 44}

    missanc.removeancestorsfrom(revs)

    if 28 in revs:

        print("Failed!")

    else:

        print("Ok")

def genlazyancestors(revs, stoprev=0, inclusive=False):

    print(

        (

            "%% lazy ancestor set for %s, stoprev = %s, inclusive = %s"

            % (revs, stoprev, inclusive)

        )

    )

    return ancestor.lazyancestors(

        graph.get, revs, stoprev=stoprev, inclusive=inclusive

    )

def printlazyancestors(s, l):

    print('membership: %r' % [n for n in l if n in s])