revset: add ^ and ~ operators from parentrevspec extension

revset: add ^ and ~ operators from parentrevspec extension

^ (Nth parent) and ~ (Nth first ancestor) are infix operators that match
certain ancestors of the set:

  set^0
  the set

  set^1 (also available as set^)
  the first parent of every changeset in set

  set^2
  the second parent of every changeset in set

  set~0
  the set

  set~1
  the first ancestor (i.e. the first parent) of every changeset in set

  set~2
  the second ancestor (i.e. first parent of first parent) of every changeset
  in set

  set~N
  the Nth ancestor (following first parents only) of every changeset in set;
  set~N is equivalent to set^1^1..., with ^1 repeated N times.

--- a/mercurial/help/revsets.txt	Sat Apr 30 10:57:13 2011 -0500
+++ b/mercurial/help/revsets.txt	Sat Apr 30 17:43:04 2011 +0200
@@ -42,6 +42,20 @@
 
 ``x - y``
   Changesets in x but not in y.
+  
+``x^n``
+  The nth parent of x, n == 0, 1, or 2.
+  For n == 0, x; for n == 1, the first parent of each changeset in x;
+  for n == 2, the second parent of changeset in x.
+
+``x~n``
+  The nth first ancestor of x; ``x~0`` is x; ``x~3`` is ``x^^^``.
+
+There is a single postfix operator:
+
+``x^``
+  Equivalent to ``x^1``, the first parent of each changeset in x.
+
 
 The following predicates are supported:
 

--- a/mercurial/revset.py	Sat Apr 30 10:57:13 2011 -0500
+++ b/mercurial/revset.py	Sat Apr 30 17:43:04 2011 +0200
@@ -13,6 +13,8 @@
 
 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)),
@@ -47,7 +49,7 @@
         elif c == '.' and program[pos:pos + 2] == '..': # look ahead carefully
             yield ('..', None, pos)
             pos += 1 # skip ahead
-        elif c in "():,-|&+!": # handle simple operators
+        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
@@ -209,6 +211,22 @@
     s = set(repo.changelog.ancestors(*args)) | set(args)
     return [r for r in subset if r in s]
 
+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 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)``.
@@ -588,6 +606,31 @@
         ps.update(cl.parentrevs(r))
     return [r for r in subset if r in ps]
 
+def parentspec(repo, subset, x, n):
+    """``set^0``
+    The set.
+    ``set^1`` (or ``set^``), ``set^2``
+    First or second parent, respectively, of all changesets in set.
+    """
+    try:
+        n = int(n[1])
+        if n not in (0,1,2):
+            raise ValueError
+    except ValueError:
+        raise error.ParseError(_("^ expects a number 0, 1, or 2"))
+    ps = set()
+    cl = repo.changelog
+    for r in getset(repo, subset, x):
+        if n == 0:
+            ps.add(r)
+        elif n == 1:
+            ps.add(cl.parentrevs(r)[0])
+        elif n == 2:
+            parents = cl.parentrevs(r)
+            if len(parents) > 1:
+                ps.add(parents[1])
+    return [r for r in subset if r in ps]
+
 def present(repo, subset, x):
     """``present(set)``
     An empty set, if any revision in set isn't found; otherwise,
@@ -769,6 +812,9 @@
     "not": notset,
     "list": listset,
     "func": func,
+    "ancestor": ancestorspec,
+    "parent": parentspec,
+    "parentpost": p1,
 }
 
 def optimize(x, small):
@@ -814,9 +860,12 @@
     elif op == 'not':
         o = optimize(x[1], not small)
         return o[0], (op, o[1])
+    elif op == 'parentpost':
+        o = optimize(x[1], small)
+        return o[0], (op, o[1])
     elif op == 'group':
         return optimize(x[1], small)
-    elif op in 'range list':
+    elif op in 'range list parent ancestorspec':
         wa, ta = optimize(x[1], small)
         wb, tb = optimize(x[2], small)
         return wa + wb, (op, ta, tb)

--- a/tests/test-revset.t	Sat Apr 30 10:57:13 2011 -0500
+++ b/tests/test-revset.t	Sat Apr 30 17:43:04 2011 +0200
@@ -374,3 +374,32 @@
   4
   2
   9
+
+parentrevspec
+
+  $ log 'merge()^0'
+  6
+  $ log 'merge()^'
+  5
+  $ log 'merge()^1'
+  5
+  $ log 'merge()^2'
+  4
+
+  $ log 'merge()~0'
+  6
+  $ log 'merge()~1'
+  5
+  $ log 'merge()~2'
+  3
+  $ log 'merge()~3'
+  1
+
+  $ log '(-3:tip)^'
+  4
+  6
+  8
+
+  $ log 'tip^foo'
+  hg: parse error: ^ expects a number 0, 1, or 2
+  [255]