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

from __future__ import absolute_import

import heapq

import re

from .i18n import _

from . import (

    encoding,

    error,

    hbisect,

    match as matchmod,

    node,

    obsolete as obsmod,

    parser,

    pathutil,

    phases,

    repoview,

    util,

)

def _revancestors(repo, revs, followfirst):

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

    if followfirst:

        cut = 1

    else:

        cut = None

    cl = repo.changelog

    def iterate():

        revs.sort(reverse=True)

        irevs = iter(revs)

        h = []

        inputrev = next(irevs, None)

        if inputrev is not None:

            heapq.heappush(h, -inputrev)

        seen = set()

        while h:

            current = -heapq.heappop(h)

            if current == inputrev:

                inputrev = next(irevs, None)

                if inputrev is not None:

                    heapq.heappush(h, -inputrev)

            if current not in seen:

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

    if followfirst:

        cut = 1

    else:

        cut = None

    def iterate():

        cl = repo.changelog

        # XXX this should be 'parentset.min()' assuming 'parentset' is a

        # smartset (and if it is not, it should.)

        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 _reachablerootspure(repo, minroot, roots, heads, includepath):

    """return (heads(::<roots> and ::<heads>))

    If includepath is True, return (<roots>::<heads>)."""

    if not roots:

        return []

    parentrevs = repo.changelog.parentrevs

    roots = set(roots)

    visit = list(heads)

    reachable = set()

    seen = {}

    # prefetch all the things! (because python is slow)

    reached = reachable.add

    dovisit = visit.append

    nextvisit = visit.pop

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

    # sys.getrecursionlimit()

    while visit:

        rev = nextvisit()

        if rev in roots:

            reached(rev)

            if not includepath:

                continue

        parents = parentrevs(rev)

        seen[rev] = parents

        for parent in parents:

            if parent >= minroot and parent not in seen:

                dovisit(parent)

    if not reachable:

        return baseset()

    if not includepath:

        return reachable

    for rev in sorted(seen):

        for parent in seen[rev]:

            if parent in reachable:

                reached(rev)

    return reachable

def reachableroots(repo, roots, heads, includepath=False):

    """return (heads(::<roots> and ::<heads>))

    If includepath is True, return (<roots>::<heads>)."""

    if not roots:

        return baseset()

    minroot = roots.min()

    roots = list(roots)

    heads = list(heads)

    try:

        revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)

    except AttributeError:

        revs = _reachablerootspure(repo, minroot, roots, heads, includepath)

    revs = baseset(revs)

    revs.sort()

    return revs

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", 18)),

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

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

           ("dagrangepost", 17)),

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

           ("dagrangepost", 17)),

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

    "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", 5)),

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

# 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

    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 "():=,-|&+!~^%": # 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 in revset '%s'") %

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

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

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

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

    if (repo.ui.configbool('devel', 'all-warnings')

            or repo.ui.configbool('devel', 'old-revset')):

        # else case should not happen, because all non-func are internal,

        # ignoring for now.

        if x[0] == 'func' and x[1][0] == 'symbol' and x[1][1] in symbols:

            repo.ui.develwarn('revset "%s" use list instead of smartset, '

                              '(upgrade your code)' % x[1][1])

    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 in subset

        or x == node.nullrev and isinstance(subset, fullreposet)):

        return baseset([x])

    return baseset()

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 = baseset([m])

    elif n == node.wdirrev:

        r = spanset(repo, m, len(repo)) + baseset([n])

    elif m == node.wdirrev:

        r = baseset([m]) + spanset(repo, len(repo) - 1, n - 1)

    elif m < n:

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

    else:

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

    # XXX We should combine with subset first: 'subset & baseset(...)'. This is

    # necessary to ensure we preserve the order in subset.

    #

    # This has performance implication, carrying the sorting over when possible

    # would be more efficient.

    return r & subset

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

    r = fullreposet(repo)

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

                         includepath=True)

    # XXX We should combine with subset first: 'subset & baseset(...)'. This is

    # necessary to ensure we preserve the order in subset.

    return xs & subset

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

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

def orset(repo, subset, *xs):

    assert xs

    if len(xs) == 1:

        return getset(repo, subset, xs[0])

    p = len(xs) // 2

    a = orset(repo, subset, *xs[:p])

    b = orset(repo, subset, *xs[p:])

    return a + b

def notset(repo, subset, x):

    return subset - getset(repo, subset, x)

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

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

def keyvaluepair(repo, subset, k, v):

    raise error.ParseError(_("can't use a key-value pair in this context"))

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

    if a[0] == 'symbol' and a[1] in symbols:

        return symbols[a[1]](repo, subset, b)

    keep = lambda fn: getattr(fn, '__doc__', None) is not None

    syms = [s for (s, fn) in symbols.items() if keep(fn)]

    raise error.UnknownIdentifier(a[1], syms)

# functions

def adds(repo, subset, x):

    """``adds(pattern)``

    Changesets that add a file matching pattern.

    The pattern without explicit kind like ``glob:`` is expected to be

    relative to the current directory and match against a file or a

    directory.

    """

    # i18n: "adds" is a keyword

    pat = getstring(x, _("adds requires a pattern"))

    return checkstatus(repo, subset, pat, 1)

def ancestor(repo, subset, x):

    """``ancestor(*changeset)``

    A greatest common ancestor of the changesets.

    Accepts 0 or more changesets.

    Will return empty list when passed no args.

    Greatest common ancestor of a single changeset is that changeset.

    """

    # i18n: "ancestor" is a keyword

    l = getlist(x)

    rl = fullreposet(repo)

    anc = None