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

    util,

)

elements = {

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

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

    "[": (21, None, None, ("subscript", 1, "]"), None),

    "#": (21, None, None, ("relation", 21), 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, "dagrangeall", ("dagrangepre", 17), ("dagrange", 17),

           "dagrangepost"),

    "..": (17, "dagrangeall", ("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),

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

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

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

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

}

keywords = {'and', 'or', 'not'}

symbols = {}

_quoteletters = {'"', "'"}

_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(b"@::"))

    [('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 getboolean(x, err):

    value = util.parsebool(getsymbol(x))

    if value is not None:

        return value

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

# cache of {spec: raw parsed tree} built internally

_treecache = {}

def _cachedtree(spec):

    # thread safe because parse() is reentrant and dict.__setitem__() is atomic

    tree = _treecache.get(spec)

    if tree is None:

        _treecache[spec] = tree = parse(spec)

    return tree

def _build(tmplspec, *repls):

    """Create raw parsed tree from a template revset statement

    >>> _build(b'f(_) and _', (b'string', b'1'), (b'symbol', b'2'))

    ('and', ('func', ('symbol', 'f'), ('string', '1')), ('symbol', '2'))

    """

    template = _cachedtree(tmplspec)

    return parser.buildtree(template, ('symbol', '_'), *repls)

def _match(patspec, tree):

    """Test if a tree matches the given pattern statement; return the matches

    >>> _match(b'f(_)', parse(b'f()'))

    >>> _match(b'f(_)', parse(b'f(1)'))

    [('func', ('symbol', 'f'), ('symbol', '1')), ('symbol', '1')]

    >>> _match(b'f(_)', parse(b'f(1, 2)'))

    """

    pattern = _cachedtree(patspec)

    return parser.matchtree(pattern, tree, ('symbol', '_'),

                            {'keyvalue', 'list'})

def _matchonly(revs, bases):

    return _match('ancestors(_) and not ancestors(_)', ('and', revs, bases))

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] == 'dagrangeall':

            return _fixops(('dagrangepost', post))

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

    elif op == 'subscript' and x[1][0] == 'relation':

        # x#y[z] ternary

        return _fixops(('relsubscript', x[1][1], x[1][2], x[2]))

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

def _analyze(x):

    if x is None:

        return x

    op = x[0]

    if op == 'minus':

        return _analyze(_build('_ and not _', *x[1:]))

    elif op == 'only':

        return _analyze(_build('only(_, _)', *x[1:]))

    elif op == 'onlypost':

        return _analyze(_build('only(_)', x[1]))

    elif op == 'dagrangeall':

        raise error.ParseError(_("can't use '::' in this context"))

    elif op == 'dagrangepre':

        return _analyze(_build('ancestors(_)', x[1]))

    elif op == 'dagrangepost':

        return _analyze(_build('descendants(_)', x[1]))

    elif op == 'negate':

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

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

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

        return x

    elif op == 'rangeall':

        return (op, None)

    elif op in {'or', 'not', 'rangepre', 'rangepost', 'parentpost'}:

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

    elif op == 'group':

        return _analyze(x[1])

    elif op in {'and', 'dagrange', 'range', 'parent', 'ancestor', 'relation',

                'subscript'}:

        ta = _analyze(x[1])

        tb = _analyze(x[2])

        return (op, ta, tb)

    elif op == 'relsubscript':

        ta = _analyze(x[1])

        tb = _analyze(x[2])

        tc = _analyze(x[3])

        return (op, ta, tb, tc)

    elif op == 'list':

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

    elif op == 'keyvalue':

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

    elif op == 'func':

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

    raise ValueError('invalid operator %r' % op)

def analyze(x):

    """Transform raw parsed tree to evaluatable tree which can be fed to