[PATCH 1 of 2 V3] revset: add origin() predicate

[Matt Harbison]

# HG changeset patch
# User Matt Harbison <matt_harbison at yahoo.com>
# Date 1341636450 14400
# Node ID f8a745b82d4c09ed08c9533123466c20fa3323e9
# Parent  2e13c1bd34dc6afda8fc7cfa22a8cd658276724f
revset: add origin() predicate

This predicate is used to find the original source of csets created by a graft,
transplant or rebase --keep.  If a copied cset is itself copied, only the
source of the original copy is selected.

    hg log -r origin()                # all src csets, anywhere
    hg log -r origin(branch(default)) # all srcs of copies on default

By following through different types of copy commands and only selecting the
original cset, the implementation differences between the copy commands are
hidden.  (A graft of a graft preserves the original source in its 'extra' map,
while transplant and rebase use the immediate source specified for the
command).

Given a repo with a cset S that is grafted to create G(S), which itself is
grafted to become G(G(S))

    o-S
   /
  o-o-G(S)
   \
    o-G(G(S))

    hg log -r origin( G(S) )      # { S }
    hg log -r origin( G(G(S)) )   # { S }, NOT { G(S) }

Even if the last graft were a transplant

    hg log -r origin( T(G(S)) )   # { S }

A rebase without --keep essentially strips the source, so providing the cset
that results to this predicate will yield an empty set.

Note that the convert extension does not currently update the 'extra' map in
its destination csets, and therefore copies made prior to the convert will be
unable to find their source.

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -875,6 +875,34 @@
 
     return [r for r in subset if r == rn]
 
+def origin(repo, subset, x):
+    """``origin([set])``
+    Changesets that were specified as a source for the grafts, transplants or
+    rebases that created the given revisions.  Omitting the optional set is the
+    same as passing all().  If a changeset created by these operations is itself
+    specified as a source for one of these operations, only the source changeset
+    for the first operation is selected.
+    """
+    if x is not None:
+        args = set(getset(repo, range(len(repo)), x))
+    else:
+        args = set(getall(repo, range(len(repo)), x))
+
+    def _firstsrc(rev):
+        src = _getrevsource(repo, rev)
+        if src is None:
+            return None
+
+        while True:
+            prev = _getrevsource(repo, src)
+
+            if prev is None:
+                return src
+            src = prev
+
+    o = set([_firstsrc(r) for r in args])
+    return [r for r in subset if r in o]
+
 def outgoing(repo, subset, x):
     """``outgoing([path])``
     Changesets not found in the specified destination repository, or the
@@ -1369,6 +1397,7 @@
     "merge": merge,
     "min": minrev,
     "modifies": modifies,
+    "origin": origin,
     "outgoing": outgoing,
     "p1": p1,
     "p2": p2,
diff --git a/tests/test-graft.t b/tests/test-graft.t
--- a/tests/test-graft.t
+++ b/tests/test-graft.t
@@ -358,3 +358,50 @@
   diff --git a/a b/b
   rename from a
   rename to b
+
+Test simple origin(), with and without args
+  $ hg log -r 'origin()'
+  changeset:   1:5d205f8b35b6
+  user:        bar
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     1
+  
+  changeset:   2:5c095ad7e90f
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     2
+  
+  changeset:   3:4c60f11aa304
+  user:        baz
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     3
+  
+  changeset:   4:9c233e8e184d
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     4
+  
+  changeset:   5:97f8bfe72746
+  branch:      stable
+  parent:      3:4c60f11aa304
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     5
+  
+  $ hg log -r 'origin(7)'
+  changeset:   2:5c095ad7e90f
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     2
+  
+Now transplant a graft to test following through copies
+  $ hg up -q 0
+  $ hg branch -q dev
+  $ hg ci -qm "dev branch"
+  $ hg --config extensions.transplant= transplant -q 7
+  $ hg log -r 'origin(.)'
+  changeset:   2:5c095ad7e90f
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     2
+