# 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

import ancestor as ancestormod

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([node.nullrev])

        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 = {

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

    "~": (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)),

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

def tokenize(program, lookup=None):

    '''

    Parse a revset statement into a stream of tokens

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

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

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

    '''

    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 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.isalnum() or c in '._@' or ord(c) > 127:

            s = pos

            pos += 1

            while pos < l: # find end of symbol

                d = program[pos]

                if not (d.isalnum() or d in "-._/@" or ord(d) > 127):

                    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)

# 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 getset(repo, subset, x):

    if not x:

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

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

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

        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 len(subset) == len(repo) or 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):

    cl = baseset(repo.changelog)

    m = getset(repo, cl, x)

    n = getset(repo, cl, 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 = spanset(repo)

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

    s = subset.set()

    return xs.filter(s.__contains__)

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

    raise error.ParseError(_("can't use a list 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)

    raise error.ParseError(_("not a function: %s") % a[1])

# 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 = spanset(repo)

    anc = None

    # (getset(repo, rl, i) for i in l) generates a list of lists

    for revs in (getset(repo, rl, i) for i in l):

        for r in revs:

            if anc is None:

                anc = repo[r]

            else:

                anc = anc.ancestor(repo[r])

    if anc is not None and anc.rev() in subset:

        return baseset([anc.rev()])

    return baseset()

def _ancestors(repo, subset, x, followfirst=False):

    args = getset(repo, spanset(repo), x)

    if not args:

        return baseset()

    s = _revancestors(repo, args, followfirst)

    return subset.filter(s.__contains__)

def ancestors(repo, subset, x):

    """``ancestors(set)``

    Changesets that are ancestors of a changeset in set.

    """

    return _ancestors(repo, subset, x)

def _firstancestors(repo, subset, x):

    # ``_firstancestors(set)``

    # Like ``ancestors(set)`` but follows only the first parents.

    return _ancestors(repo, subset, x, followfirst=True)

def ancestorspec(repo, subset, x, n):