# 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 bookmarks as bookmarksmod

import match as matchmod

from i18n import _

import encoding

def _revancestors(repo, revs, followfirst):

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

    cut = followfirst and 1 or None

    cl = repo.changelog

    visit = util.deque(revs)

    seen = set([node.nullrev])

    while visit:

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

            if parent not in seen:

                visit.append(parent)

                seen.add(parent)

                yield parent

def _revdescendants(repo, revs, followfirst):

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

    cut = followfirst and 1 or None

    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

        return

    seen = set(revs)

    for i in xrange(first + 1, len(cl)):

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

            if x != nullrev and x in seen:

                seen.add(i)

                yield i

                break

def _revsbetween(repo, roots, heads):

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

    sets."""

    if not roots:

        return []

    parentrevs = repo.changelog.parentrevs

    visit = 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 []

    for rev in sorted(seen):

        for parent in seen[rev]:

            if parent in reachable:

                reachable.add(rev)

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

    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)

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

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

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 [-1]

    if len(subset) == len(repo) or x in subset:

        return [x]

    return []

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, subset, x)

    if not m:

        m = getset(repo, range(len(repo)), x)

    n = getset(repo, subset, y)

    if not n:

        n = getset(repo, range(len(repo)), y)

    if not m or not n:

        return []

    m, n = m[0], n[-1]

    if m < n:

        r = range(m, n + 1)

    else:

        r = range(m, n - 1, -1)

    s = set(subset)

    return [x for x in r if x in s]

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

    if subset:

        r = range(len(repo))

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

        s = set(subset)

        return [r for r in xs if r in s]

    return []

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)

    s = set(xl)

    yl = getset(repo, [r for r in subset if r not in s], y)

    return xl + yl

def notset(repo, subset, x):

    s = set(getset(repo, subset, x))

    return [r for r in subset if r not in s]

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.

    """

    # i18n: "adds" is a keyword

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

    return checkstatus(repo, subset, pat, 1)

def ancestor(repo, subset, x):

    """``ancestor(single, single)``

    Greatest common ancestor of the two changesets.

    """

    # i18n: "ancestor" is a keyword

    l = getargs(x, 2, 2, _("ancestor requires two arguments"))

    r = range(len(repo))

    a = getset(repo, r, l[0])

    b = getset(repo, r, l[1])

    if len(a) != 1 or len(b) != 1:

        # i18n: "ancestor" is a keyword

        raise error.ParseError(_("ancestor arguments must be single revisions"))

    an = [repo[a[0]].ancestor(repo[b[0]]).rev()]

    return [r for r in an if r in subset]

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

    args = getset(repo, range(len(repo)), x)

    if not args:

        return []

    s = set(_revancestors(repo, args, followfirst)) | set(args)

    return [r for r in subset if r in s]

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

    """``set~n``

    Changesets that are the Nth ancestor (first parents only) of a changeset

    in set.

    """

    try:

        n = int(n[1])

    except (TypeError, ValueError):

        raise error.ParseError(_("~ expects a number"))

    ps = set()

    cl = repo.changelog

    for r in getset(repo, subset, x):

        for i in range(n):

            r = cl.parentrevs(r)[0]

        ps.add(r)

    return [r for r in subset if r in ps]

def author(repo, subset, x):

    """``author(string)``

    Alias for ``user(string)``.

    """

    # i18n: "author" is a keyword

    n = encoding.lower(getstring(x, _("author requires a string")))

    kind, pattern, matcher = _substringmatcher(n)

    return [r for r in subset if matcher(encoding.lower(repo[r].user()))]

def bisect(repo, subset, x):

    """``bisect(string)``

    Changesets marked in the specified bisect status:

    - ``good``, ``bad``, ``skip``: csets explicitly marked as good/bad/skip

    - ``goods``, ``bads``      : csets topologicaly good/bad

    - ``range``              : csets taking part in the bisection

    - ``pruned``             : csets that are goods, bads or skipped

    - ``untested``           : csets whose fate is yet unknown

    - ``ignored``            : csets ignored due to DAG topology

    - ``current``            : the cset currently being bisected

    """

    status = getstring(x, _("bisect requires a string")).lower()

    state = set(hbisect.get(repo, status))

    return [r for r in subset if r in state]

# Backward-compatibility

# - no help entry so that we do not advertise it any more

def bisected(repo, subset, x):

    return bisect(repo, subset, x)

def bookmark(repo, subset, x):

    """``bookmark([name])``

    The named bookmark or all bookmarks.

    If `name` starts with `re:`, the remainder of the name is treated as

    a regular expression. To match a bookmark that actually starts with `re:`,

    use the prefix `literal:`.

    """

    # i18n: "bookmark" is a keyword

    args = getargs(x, 0, 1, _('bookmark takes one or no arguments'))

    if args:

        bm = getstring(args[0],

                       # i18n: "bookmark" is a keyword

                       _('the argument to bookmark must be a string'))

        kind, pattern, matcher = _stringmatcher(bm)

        if kind == 'literal':

            bmrev = bookmarksmod.listbookmarks(repo).get(bm, None)

            if not bmrev:

                raise util.Abort(_("bookmark '%s' does not exist") % bm)

            bmrev = repo[bmrev].rev()

            return [r for r in subset if r == bmrev]

        else:

            matchrevs = set()

            for name, bmrev in bookmarksmod.listbookmarks(repo).iteritems():

                if matcher(name):

                    matchrevs.add(bmrev)

            if not matchrevs:

                raise util.Abort(_("no bookmarks exist that match '%s'")

                                 % pattern)

            bmrevs = set()

            for bmrev in matchrevs:

                bmrevs.add(repo[bmrev].rev())

            return [r for r in subset if r in bmrevs]

    bms = set([repo[r].rev()

               for r in bookmarksmod.listbookmarks(repo).values()])

    return [r for r in subset if r in bms]

def branch(repo, subset, x):

    """``branch(string or set)``

    All changesets belonging to the given branch or the branches of the given

    changesets.

    If `string` starts with `re:`, the remainder of the name is treated as

    a regular expression. To match a branch that actually starts with `re:`,

    use the prefix `literal:`.

    """

    try:

        b = getstring(x, '')

    except error.ParseError:

        # not a string, but another revspec, e.g. tip()

        pass

    else:

        kind, pattern, matcher = _stringmatcher(b)

        if kind == 'literal':

            # note: falls through to the revspec case if no branch with

            # this name exists

            if pattern in repo.branchmap():

                return [r for r in subset if matcher(repo[r].branch())]

        else:

            return [r for r in subset if matcher(repo[r].branch())]

    s = getset(repo, range(len(repo)), x)

    b = set()

    for r in s:

        b.add(repo[r].branch())

    s = set(s)

    return [r for r in subset if r in s or repo[r].branch() in b]

def checkstatus(repo, subset, pat, field):

    m = None

    s = []

    hasset = matchmod.patkind(pat) == 'set'

    fname = None

    for r in subset:

        c = repo[r]

        if not m or hasset:

            m = matchmod.match(repo.root, repo.getcwd(), [pat], ctx=c)

            if not m.anypats() and len(m.files()) == 1:

                fname = m.files()[0]

        if fname is not None:

            if fname not in c.files():

                continue

        else:

            for f in c.files():

                if m(f):

                    break

            else:

                continue

        files = repo.status(c.p1().node(), c.node())[field]

        if fname is not None:

            if fname in files:

                s.append(r)

        else:

            for f in files:

                if m(f):

                    s.append(r)

                    break

    return s

def _children(repo, narrow, parentset):

    cs = set()

    pr = repo.changelog.parentrevs

    for r in narrow:

        for p in pr(r):

            if p in parentset:

                cs.add(r)

    return cs

def children(repo, subset, x):

    """``children(set)``

    Child changesets of changesets in set.

    """

    s = set(getset(repo, range(len(repo)), x))

    cs = _children(repo, subset, s)

    return [r for r in subset if r in cs]

def closed(repo, subset, x):

    """``closed()``

    Changeset is closed.

    """

    # i18n: "closed" is a keyword

    getargs(x, 0, 0, _("closed takes no arguments"))

    return [r for r in subset if repo[r].closesbranch()]

def contains(repo, subset, x):

    """``contains(pattern)``

    Revision contains a file matching pattern. See :hg:`help patterns`

    for information about file patterns.

    """

    # i18n: "contains" is a keyword

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

    m = None

    s = []

    if not matchmod.patkind(pat):

        for r in subset:

            if pat in repo[r]:

                s.append(r)

    else:

        for r in subset: