# revset.py - revision set queries for mercurial

#

# Copyright 2010 Matt Mackall <mpm@selenic.com>

#

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

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

import re

import parser, util, error, discovery, hbisect, phases

import node

import heapq

import match as matchmod

from i18n import _

import encoding

import obsolete as obsmod

import pathutil

import repoview

def _revancestors(repo, revs, followfirst):

    """Like revlog.ancestors(), but supports followfirst."""

    cut = followfirst and 1 or None

    cl = repo.changelog

    def iterate():

        revqueue, revsnode = None, None

        h = []

        revs.sort(reverse=True)

        revqueue = util.deque(revs)

        if revqueue:

            revsnode = revqueue.popleft()

            heapq.heappush(h, -revsnode)

        seen = set()

        while h:

            current = -heapq.heappop(h)

            if current not in seen:

                if revsnode and current == revsnode:

                    if revqueue:

                        revsnode = revqueue.popleft()

                        heapq.heappush(h, -revsnode)

                seen.add(current)

                yield current

                for parent in cl.parentrevs(current)[:cut]:

                    if parent != node.nullrev:

                        heapq.heappush(h, -parent)

    return generatorset(iterate(), iterasc=False)

def _revdescendants(repo, revs, followfirst):

    """Like revlog.descendants() but supports followfirst."""

    cut = followfirst and 1 or None

    def iterate():

        cl = repo.changelog

        first = min(revs)

        nullrev = node.nullrev

        if first == nullrev:

            # Are there nodes with a null first parent and a non-null

            # second one? Maybe. Do we care? Probably not.

            for i in cl:

                yield i

        else:

            seen = set(revs)

            for i in cl.revs(first + 1):

                for x in cl.parentrevs(i)[:cut]:

                    if x != nullrev and x in seen:

                        seen.add(i)

                        yield i

                        break

    return generatorset(iterate(), iterasc=True)

def _revsbetween(repo, roots, heads):

    """Return all paths between roots and heads, inclusive of both endpoint

    sets."""

    if not roots:

        return baseset()

    parentrevs = repo.changelog.parentrevs

    visit = list(heads)

    reachable = set()

    seen = {}

    minroot = min(roots)

    roots = set(roots)

    # open-code the post-order traversal due to the tiny size of

    # sys.getrecursionlimit()

    while visit:

        rev = visit.pop()

        if rev in roots:

            reachable.add(rev)

        parents = parentrevs(rev)

        seen[rev] = parents

        for parent in parents:

            if parent >= minroot and parent not in seen:

                visit.append(parent)

    if not reachable:

        return baseset()

    for rev in sorted(seen):

        for parent in seen[rev]:

            if parent in reachable:

                reachable.add(rev)

    return baseset(sorted(reachable))

elements = {

    "(": (21, ("group", 1, ")"), ("func", 1, ")")),

    "##": (20, None, ("_concat", 20)),

    "~": (18, None, ("ancestor", 18)),

    "^": (18, None, ("parent", 18), ("parentpost", 18)),

    "-": (5, ("negate", 19), ("minus", 5)),

    "::": (17, ("dagrangepre", 17), ("dagrange", 17),

           ("dagrangepost", 17)),

    "..": (17, ("dagrangepre", 17), ("dagrange", 17),

           ("dagrangepost", 17)),

    ":": (15, ("rangepre", 15), ("range", 15), ("rangepost", 15)),

    "not": (10, ("not", 10)),

    "!": (10, ("not", 10)),

    "and": (5, None, ("and", 5)),

    "&": (5, None, ("and", 5)),

    "%": (5, None, ("only", 5), ("onlypost", 5)),

    "or": (4, None, ("or", 4)),

    "|": (4, None, ("or", 4)),

    "+": (4, None, ("or", 4)),

    ",": (2, None, ("list", 2)),

    ")": (0, None, None),

    "symbol": (0, ("symbol",), None),

    "string": (0, ("string",), None),

    "end": (0, None, None),

}

keywords = set(['and', 'or', 'not'])

# default set of valid characters for the initial letter of symbols

_syminitletters = set(c for c in [chr(i) for i in xrange(256)]

                      if c.isalnum() or c in '._@' or ord(c) > 127)

# default set of valid characters for non-initial letters of symbols

_symletters = set(c for c in  [chr(i) for i in xrange(256)]

                  if c.isalnum() or c in '-._/@' or ord(c) > 127)

def tokenize(program, lookup=None, syminitletters=None, symletters=None):

    '''

    Parse a revset statement into a stream of tokens

    ``syminitletters`` is the set of valid characters for the initial

    letter of symbols.

    By default, character ``c`` is recognized as valid for initial

    letter of symbols, if ``c.isalnum() or c in '._@' or ord(c) > 127``.

    ``symletters`` is the set of valid characters for non-initial

    letters of symbols.

    By default, character ``c`` is recognized as valid for non-initial

    letters of symbols, if ``c.isalnum() or c in '-._/@' or ord(c) > 127``.

    Check that @ is a valid unquoted token character (issue3686):

    >>> list(tokenize("@::"))

    [('symbol', '@', 0), ('::', None, 1), ('end', None, 3)]

    '''

    if syminitletters is None:

        syminitletters = _syminitletters

    if symletters is None:

        symletters = _symletters

    pos, l = 0, len(program)

    while pos < l:

        c = program[pos]

        if c.isspace(): # skip inter-token whitespace

            pass

        elif c == ':' and program[pos:pos + 2] == '::': # look ahead carefully

            yield ('::', None, pos)

            pos += 1 # skip ahead

        elif c == '.' and program[pos:pos + 2] == '..': # look ahead carefully

            yield ('..', None, pos)

            pos += 1 # skip ahead

        elif c == '#' and program[pos:pos + 2] == '##': # look ahead carefully

            yield ('##', None, pos)

            pos += 1 # skip ahead

        elif c in "():,-|&+!~^%": # handle simple operators

            yield (c, None, pos)

        elif (c in '"\'' or c == 'r' and

              program[pos:pos + 2] in ("r'", 'r"')): # handle quoted strings

            if c == 'r':

                pos += 1

                c = program[pos]

                decode = lambda x: x

            else:

                decode = lambda x: x.decode('string-escape')

            pos += 1

            s = pos

            while pos < l: # find closing quote

                d = program[pos]

                if d == '\\': # skip over escaped characters

                    pos += 2

                    continue

                if d == c:

                    yield ('string', decode(program[s:pos]), s)

                    break

                pos += 1

            else:

                raise error.ParseError(_("unterminated string"), s)

        # gather up a symbol/keyword

        elif c in syminitletters:

            s = pos

            pos += 1

            while pos < l: # find end of symbol

                d = program[pos]

                if d not in symletters:

                    break

                if d == '.' and program[pos - 1] == '.': # special case for ..

                    pos -= 1

                    break

                pos += 1

            sym = program[s:pos]

            if sym in keywords: # operator keywords

                yield (sym, None, s)

            elif '-' in sym:

                # some jerk gave us foo-bar-baz, try to check if it's a symbol

                if lookup and lookup(sym):

                    # looks like a real symbol

                    yield ('symbol', sym, s)

                else:

                    # looks like an expression

                    parts = sym.split('-')

                    for p in parts[:-1]:

                        if p: # possible consecutive -

                            yield ('symbol', p, s)

                        s += len(p)

                        yield ('-', None, pos)

                        s += 1

                    if parts[-1]: # possible trailing -

                        yield ('symbol', parts[-1], s)

            else:

                yield ('symbol', sym, s)

            pos -= 1

        else:

            raise error.ParseError(_("syntax error"), pos)

        pos += 1

    yield ('end', None, pos)

def parseerrordetail(inst):

    """Compose error message from specified ParseError object

    """

    if len(inst.args) > 1:

        return _('at %s: %s') % (inst.args[1], inst.args[0])

    else:

        return inst.args[0]

# helpers

def getstring(x, err):

    if x and (x[0] == 'string' or x[0] == 'symbol'):

        return x[1]

    raise error.ParseError(err)

def getlist(x):

    if not x:

        return []

    if x[0] == 'list':

        return getlist(x[1]) + [x[2]]

    return [x]

def getargs(x, min, max, err):

    l = getlist(x)

    if len(l) < min or (max >= 0 and len(l) > max):

        raise error.ParseError(err)

    return l

def isvalidsymbol(tree):

    """Examine whether specified ``tree`` is valid ``symbol`` or not

    """

    return tree[0] == 'symbol' and len(tree) > 1

def getsymbol(tree):

    """Get symbol name from valid ``symbol`` in ``tree``

    This assumes that ``tree`` is already examined by ``isvalidsymbol``.

    """

    return tree[1]

def isvalidfunc(tree):

    """Examine whether specified ``tree`` is valid ``func`` or not

    """

    return tree[0] == 'func' and len(tree) > 1 and isvalidsymbol(tree[1])

def getfuncname(tree):

    """Get function name from valid ``func`` in ``tree``

    This assumes that ``tree`` is already examined by ``isvalidfunc``.

    """

    return getsymbol(tree[1])

def getfuncargs(tree):

    """Get list of function arguments from valid ``func`` in ``tree``

    This assumes that ``tree`` is already examined by ``isvalidfunc``.

    """

    if len(tree) > 2:

        return getlist(tree[2])

    else:

        return []

def getset(repo, subset, x):

    if not x:

        raise error.ParseError(_("missing argument"))

    s = methods[x[0]](repo, subset, *x[1:])

    if util.safehasattr(s, 'isascending'):

        return s

    return baseset(s)

def _getrevsource(repo, r):

    extra = repo[r].extra()

    for label in ('source', 'transplant_source', 'rebase_source'):

        if label in extra:

            try:

                return repo[extra[label]].rev()

            except error.RepoLookupError:

                pass

    return None

# operator methods

def stringset(repo, subset, x):

    x = repo[x].rev()

    if x == -1 and len(subset) == len(repo):

        return baseset([-1])

    if x in subset:

        return baseset([x])

    return baseset()

def symbolset(repo, subset, x):

    if x in symbols:

        raise error.ParseError(_("can't use %s here") % x)

    return stringset(repo, subset, x)

def rangeset(repo, subset, x, y):

    m = getset(repo, fullreposet(repo), x)

    n = getset(repo, fullreposet(repo), y)

    if not m or not n:

        return baseset()

    m, n = m.first(), n.last()

    if m < n:

        r = spanset(repo, m, n + 1)

    else:

        r = spanset(repo, m, n - 1)

    return r & subset

def dagrange(repo, subset, x, y):

    r = fullreposet(repo)

    xs = _revsbetween(repo, getset(repo, r, x), getset(repo, r, y))

    return xs & subset

def andset(repo, subset, x, y):

    return getset(repo, getset(repo, subset, x), y)

def orset(repo, subset, x, y):

    xl = getset(repo, subset, x)

    yl = getset(repo, subset - xl, y)

    return xl + yl

def notset(repo, subset, x):

    return subset - getset(repo, subset, x)

def listset(repo, subset, a, b):