# revsetlang.py - parser, tokenizer and utility for revision set language

#

# 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.

from __future__ import absolute_import

import string

from .i18n import _

from . import (

    error,

    node,

    parser,

    pycompat,

)

elements = {

    # token-type: binding-strength, primary, prefix, infix, suffix

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    "=": (3, None, None, ("keyvalue", 3), None),

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

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

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

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

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

}

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

_quoteletters = set(['"', "'"])

_simpleopletters = set(pycompat.iterbytestr("():=,-|&+!~^%"))

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

_syminitletters = set(pycompat.iterbytestr(

    string.ascii_letters.encode('ascii') +

    string.digits.encode('ascii') +

    '._@')) | set(map(pycompat.bytechr, xrange(128, 256)))

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

_symletters = _syminitletters | set(pycompat.iterbytestr('-/'))

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)]

    '''

    program = pycompat.bytestr(program)

    if syminitletters is None:

        syminitletters = _syminitletters

    if symletters is None:

        symletters = _symletters

    if program and lookup:

        # attempt to parse old-style ranges first to deal with

        # things like old-tag which contain query metacharacters

        parts = program.split(':', 1)

        if all(lookup(sym) for sym in parts if sym):

            if parts[0]:

                yield ('symbol', parts[0], 0)

            if len(parts) > 1:

                s = len(parts[0])

                yield (':', None, s)

                if parts[1]:

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

            yield ('end', None, len(program))

            return

    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 _simpleopletters: # handle simple operators

            yield (c, None, pos)

        elif (c in _quoteletters 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 = parser.unescapestr

            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 in revset '%s'") %

                                   program, pos)

        pos += 1

    yield ('end', None, pos)

# helpers

_notset = object()

def getsymbol(x):

    if x and x[0] == 'symbol':

        return x[1]

    raise error.ParseError(_('not a symbol'))

def getstring(x, err):

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

        return x[1]

    raise error.ParseError(err)

def getinteger(x, err, default=_notset):

    if not x and default is not _notset:

        return default

    try:

        return int(getstring(x, err))

    except ValueError:

        raise error.ParseError(err)

def getlist(x):

    if not x:

        return []

    if x[0] == 'list':

        return list(x[1:])

    return [x]

def getrange(x, err):

    if not x:

        raise error.ParseError(err)

    op = x[0]

    if op == 'range':

        return x[1], x[2]

    elif op == 'rangepre':

        return None, x[1]

    elif op == 'rangepost':

        return x[1], None

    elif op == 'rangeall':

        return None, None

    raise error.ParseError(err)

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 getargsdict(x, funcname, keys):

    return parser.buildargsdict(getlist(x), funcname, parser.splitargspec(keys),

                                keyvaluenode='keyvalue', keynode='symbol')

# Constants for ordering requirement, used in _analyze():

#

# If 'define', any nested functions and operations can change the ordering of

# the entries in the set. If 'follow', any nested functions and operations

# should take the ordering specified by the first operand to the '&' operator.

#

# For instance,

#

#   X & (Y | Z)

#   ^   ^^^^^^^

#   |   follow

#   define

#

# will be evaluated as 'or(y(x()), z(x()))', where 'x()' can change the order

# of the entries in the set, but 'y()', 'z()' and 'or()' shouldn't.

#

# 'any' means the order doesn't matter. For instance,

#

#   X & !Y

#        ^

#        any

#

# 'y()' can either enforce its ordering requirement or take the ordering

# specified by 'x()' because 'not()' doesn't care the order.

#

# Transition of ordering requirement:

#

# 1. starts with 'define'

# 2. shifts to 'follow' by 'x & y'

# 3. changes back to 'define' on function call 'f(x)' or function-like

#    operation 'x (f) y' because 'f' may have its own ordering requirement

#    for 'x' and 'y' (e.g. 'first(x)')

#

anyorder = 'any'        # don't care the order

defineorder = 'define'  # should define the order

followorder = 'follow'  # must follow the current order

# transition table for 'x & y', from the current expression 'x' to 'y'

_tofolloworder = {

    anyorder: anyorder,

    defineorder: followorder,

    followorder: followorder,

}

def _matchonly(revs, bases):

    """

    >>> f = lambda *args: _matchonly(*map(parse, args))

    >>> f('ancestors(A)', 'not ancestors(B)')

    ('list', ('symbol', 'A'), ('symbol', 'B'))

    """

    if (revs is not None

        and revs[0] == 'func'

        and getsymbol(revs[1]) == 'ancestors'

        and bases is not None

        and bases[0] == 'not'

        and bases[1][0] == 'func'

        and getsymbol(bases[1][1]) == 'ancestors'):

        return ('list', revs[2], bases[1][2])

def _fixops(x):

    """Rewrite raw parsed tree to resolve ambiguous syntax which cannot be

    handled well by our simple top-down parser"""

    if not isinstance(x, tuple):

        return x

    op = x[0]

    if op == 'parent':

        # x^:y means (x^) : y, not x ^ (:y)

        # x^:  means (x^) :,   not x ^ (:)

        post = ('parentpost', x[1])

        if x[2][0] == 'dagrangepre':

            return _fixops(('dagrange', post, x[2][1]))

        elif x[2][0] == 'rangepre':

            return _fixops(('range', post, x[2][1]))

        elif x[2][0] == 'rangeall':

            return _fixops(('rangepost', post))

    elif op == 'or':

        # make number of arguments deterministic:

        # x + y + z -> (or x y z) -> (or (list x y z))

        return (op, _fixops(('list',) + x[1:]))

    return (op,) + tuple(_fixops(y) for y in x[1:])

def _analyze(x, order):

    if x is None:

        return x

    op = x[0]

    if op == 'minus':

        return _analyze(('and', x[1], ('not', x[2])), order)

    elif op == 'only':

        t = ('func', ('symbol', 'only'), ('list', x[1], x[2]))

        return _analyze(t, order)

    elif op == 'onlypost':

        return _analyze(('func', ('symbol', 'only'), x[1]), order)

    elif op == 'dagrangepre':

        return _analyze(('func', ('symbol', 'ancestors'), x[1]), order)

    elif op == 'dagrangepost':

        return _analyze(('func', ('symbol', 'descendants'), x[1]), order)

    elif op == 'negate':

        s = getstring(x[1], _("can't negate that"))

        return _analyze(('string', '-' + s), order)

    elif op in ('string', 'symbol'):

        return x

    elif op == 'and':

        ta = _analyze(x[1], order)

        tb = _analyze(x[2], _tofolloworder[order])

        return (op, ta, tb, order)

    elif op == 'or':

        return (op, _analyze(x[1], order), order)

    elif op == 'not':

        return (op, _analyze(x[1], anyorder), order)

    elif op == 'rangeall':

        return (op, None, order)

    elif op in ('rangepre', 'rangepost', 'parentpost'):

        return (op, _analyze(x[1], defineorder), order)

    elif op == 'group':

        return _analyze(x[1], order)

    elif op in ('dagrange', 'range', 'parent', 'ancestor'):

        ta = _analyze(x[1], defineorder)

        tb = _analyze(x[2], defineorder)

        return (op, ta, tb, order)

    elif op == 'list':

        return (op,) + tuple(_analyze(y, order) for y in x[1:])

    elif op == 'keyvalue':

        return (op, x[1], _analyze(x[2], order))

    elif op == 'func':

        f = getsymbol(x[1])

        d = defineorder