diff --git a/mercurial/registrar.py b/mercurial/registrar.py
--- a/mercurial/registrar.py
+++ b/mercurial/registrar.py
@@ -7,6 +7,8 @@
 
 from __future__ import absolute_import
 
+import inspect
+
 from . import (
     configitems,
     error,
@@ -166,6 +168,14 @@
     Optional argument 'takeorder' indicates whether a predicate function
     takes ordering policy as the last argument.
 
+    Optional argument 'takesubset' indicates whether a predicate function
+    takes subset as its second argument. By default, takesubset is None and
+    will be inferred from function signature.
+
+    New revset functions are recommended to either take none of subset and
+    order, or take both (and use ``revset.intersect``) so it can handle
+    ordering correctly.
+
     'revsetpredicate' instance in example above can be used to
     decorate multiple functions.
 
@@ -178,9 +188,22 @@
     _getname = _funcregistrarbase._parsefuncdecl
     _docformat = "``%s``\n    %s"
 
-    def _extrasetup(self, name, func, safe=False, takeorder=False):
+    def _extrasetup(self, name, func, safe=False, takeorder=False,
+                    takesubset=None):
+        if takeorder:
+            if takesubset is False:
+                raise error.ProgrammingError(
+                    'takesubset cannot be False when takeorder is True')
+            takesubset = True
+
+        if takesubset is None:
+            # detect from signature
+            args = inspect.getargspec(func).args
+            takesubset = (len(args) >= 3)
+
         func._safe = safe
         func._takeorder = takeorder
+        func._takesubset = takesubset
 
 class filesetpredicate(_funcregistrarbase):
     """Decorator to register fileset predicate
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -200,9 +200,9 @@
         # from ancestors() and descendants() predicates
         if n <= 0:
             n = -n
-            return _ancestors(repo, subset, x, startdepth=n, stopdepth=n + 1)
+            return _ancestors(repo, x, startdepth=n, stopdepth=n + 1)
         else:
-            return _descendants(repo, subset, x, startdepth=n, stopdepth=n + 1)
+            return _descendants(repo, x, startdepth=n, stopdepth=n + 1)
 
     raise error.UnknownIdentifier(rel, ['generations'])
 
@@ -220,9 +220,18 @@
     f = getsymbol(a)
     if f in symbols:
         func = symbols[f]
-        if getattr(func, '_takeorder', False):
-            return func(repo, subset, b, order)
-        return func(repo, subset, b)
+        takesubset = getattr(func, '_takesubset', True)
+        takeorder = getattr(func, '_takeorder', False)
+        if takesubset:
+            if takeorder:
+                return func(repo, subset, b, order)
+            else:
+                # do we want warning since it may have ordering issues?
+                return func(repo, subset, b)
+        else:
+            assert not takeorder
+            newset = func(repo, b)
+            return intersect(subset, newset, order)
 
     keep = lambda fn: getattr(fn, '__doc__', None) is not None
 
@@ -247,18 +256,18 @@
 predicate = registrar.revsetpredicate()
 
 @predicate('_destupdate')
-def _destupdate(repo, subset, x):
+def _destupdate(repo, x):
     # experimental revset for update destination
     args = getargsdict(x, 'limit', 'clean')
-    return subset & baseset([destutil.destupdate(repo, **args)[0]])
+    return baseset([destutil.destupdate(repo, **args)[0]])
 
 @predicate('_destmerge')
-def _destmerge(repo, subset, x):
+def _destmerge(repo, x):
     # experimental revset for merge destination
     sourceset = None
     if x is not None:
         sourceset = getset(repo, fullreposet(repo), x)
-    return subset & baseset([destutil.destmerge(repo, sourceset=sourceset)])
+    return baseset([destutil.destmerge(repo, sourceset=sourceset)])
 
 @predicate('adds(pattern)', safe=True)
 def adds(repo, subset, x):
@@ -297,16 +306,15 @@
         return baseset([anc.rev()])
     return baseset()
 
-def _ancestors(repo, subset, x, followfirst=False, startdepth=None,
-               stopdepth=None):
+def _ancestors(repo, x, followfirst=False, startdepth=None, stopdepth=None):
     heads = getset(repo, fullreposet(repo), x)
     if not heads:
         return baseset()
     s = dagop.revancestors(repo, heads, followfirst, startdepth, stopdepth)
-    return subset & s
+    return s
 
 @predicate('ancestors(set[, depth])', safe=True)
-def ancestors(repo, subset, x):
+def ancestors(repo, x):
     """Changesets that are ancestors of changesets in set, including the
     given changesets themselves.
 
@@ -331,16 +339,16 @@
         if n < 0:
             raise error.ParseError(_("negative depth"))
         stopdepth = n + 1
-    return _ancestors(repo, subset, args['set'],
+    return _ancestors(repo, args['set'],
                       startdepth=startdepth, stopdepth=stopdepth)
 
 @predicate('_firstancestors', safe=True)
-def _firstancestors(repo, subset, x):
+def _firstancestors(repo, x):
     # ``_firstancestors(set)``
     # Like ``ancestors(set)`` but follows only the first parents.
-    return _ancestors(repo, subset, x, followfirst=True)
+    return _ancestors(repo, x, followfirst=True)
 
-def _childrenspec(repo, subset, x, n, order):
+def _childrenspec(repo, x, n):
     """Changesets that are the Nth child of a changeset
     in set.
     """
@@ -356,7 +364,7 @@
             r = c[0].rev()
         else:
             cs.add(r)
-    return subset & cs
+    return cs
 
 def ancestorspec(repo, subset, x, n, order):
     """``set~n``
@@ -366,7 +374,7 @@
     n = getinteger(n, _("~ expects a number"))
     if n < 0:
         # children lookup
-        return _childrenspec(repo, subset, x, -n, order)
+        return intersect(subset, _childrenspec(repo, x, -n), order)
     ps = set()
     cl = repo.changelog
     for r in getset(repo, fullreposet(repo), x):
@@ -389,7 +397,7 @@
                          condrepr=('<user %r>', n))
 
 @predicate('bisect(string)', safe=True)
-def bisect(repo, subset, x):
+def bisect(repo, x):
     """Changesets marked in the specified bisect status:
 
     - ``good``, ``bad``, ``skip``: csets explicitly marked as good/bad/skip
@@ -403,16 +411,16 @@
     # i18n: "bisect" is a keyword
     status = getstring(x, _("bisect requires a string")).lower()
     state = set(hbisect.get(repo, status))
-    return subset & state
+    return state
 
 # Backward-compatibility
 # - no help entry so that we do not advertise it any more
 @predicate('bisected', safe=True)
-def bisected(repo, subset, x):
-    return bisect(repo, subset, x)
+def bisected(repo, x):
+    return bisect(repo, x)
 
 @predicate('bookmark([name])', safe=True)
-def bookmark(repo, subset, x):
+def bookmark(repo, x):
     """The named bookmark or all bookmarks.
 
     Pattern matching is supported for `name`. See :hg:`help revisions.patterns`.
@@ -444,7 +452,7 @@
     else:
         bms = {repo[r].rev() for r in repo._bookmarks.values()}
     bms -= {node.nullrev}
-    return subset & bms
+    return bms
 
 @predicate('branch(string or set)', safe=True)
 def branch(repo, subset, x):
@@ -499,7 +507,7 @@
     return phasedivergent(repo, subset, x)
 
 @predicate('phasedivergent()', safe=True)
-def phasedivergent(repo, subset, x):
+def phasedivergent(repo, x):
     """Mutable changesets marked as successors of public changesets.
 
     Only non-public and non-obsolete changesets can be `phasedivergent`.
@@ -508,10 +516,10 @@
     # i18n: "phasedivergent" is a keyword
     getargs(x, 0, 0, _("phasedivergent takes no arguments"))
     phasedivergent = obsmod.getrevs(repo, 'phasedivergent')
-    return subset & phasedivergent
+    return phasedivergent
 
 @predicate('bundle()', safe=True)
-def bundle(repo, subset, x):
+def bundle(repo, x):
     """Changesets in the bundle.
 
     Bundle must be specified by the -R option."""
@@ -520,7 +528,7 @@
         bundlerevs = repo.changelog.bundlerevs
     except AttributeError:
         raise error.Abort(_("no bundle provided - specify with -R"))
-    return subset & bundlerevs
+    return bundlerevs
 
 def checkstatus(repo, subset, pat, field):
     hasset = matchmod.patkind(pat) == 'set'
@@ -663,16 +671,15 @@
     return subset.filter(lambda r: matcher(repo[r].description()),
                          condrepr=('<desc %r>', ds))
 
-def _descendants(repo, subset, x, followfirst=False, startdepth=None,
-                 stopdepth=None):
+def _descendants(repo, x, followfirst=False, startdepth=None, stopdepth=None):
     roots = getset(repo, fullreposet(repo), x)
     if not roots:
         return baseset()
     s = dagop.revdescendants(repo, roots, followfirst, startdepth, stopdepth)
-    return subset & s
+    return s
 
 @predicate('descendants(set[, depth])', safe=True)
-def descendants(repo, subset, x):
+def descendants(repo, x):
     """Changesets which are descendants of changesets in set, including the
     given changesets themselves.
 
@@ -697,14 +704,14 @@
         if n < 0:
             raise error.ParseError(_("negative depth"))
         stopdepth = n + 1
-    return _descendants(repo, subset, args['set'],
+    return _descendants(repo, args['set'],
                         startdepth=startdepth, stopdepth=stopdepth)
 
 @predicate('_firstdescendants', safe=True)
-def _firstdescendants(repo, subset, x):
+def _firstdescendants(repo, x):
     # ``_firstdescendants(set)``
     # Like ``descendants(set)`` but follows only the first parents.
-    return _descendants(repo, subset, x, followfirst=True)
+    return _descendants(repo, x, followfirst=True)
 
 @predicate('destination([set])', safe=True)
 def destination(repo, subset, x):
@@ -760,7 +767,7 @@
     return contentdivergent(repo, subset, x)
 
 @predicate('contentdivergent()', safe=True)
-def contentdivergent(repo, subset, x):
+def contentdivergent(repo, x):
     """
     Final successors of changesets with an alternative set of final
     successors. (EXPERIMENTAL)
@@ -768,16 +775,16 @@
     # i18n: "contentdivergent" is a keyword
     getargs(x, 0, 0, _("contentdivergent takes no arguments"))
     contentdivergent = obsmod.getrevs(repo, 'contentdivergent')
-    return subset & contentdivergent
+    return contentdivergent
 
 @predicate('extinct()', safe=True)
-def extinct(repo, subset, x):
+def extinct(repo, x):
     """Obsolete changesets with obsolete descendants only.
     """
     # i18n: "extinct" is a keyword
     getargs(x, 0, 0, _("extinct takes no arguments"))
     extincts = obsmod.getrevs(repo, 'extinct')
-    return subset & extincts
+    return extincts
 
 @predicate('extra(label, [value])', safe=True)
 def extra(repo, subset, x):
@@ -810,7 +817,7 @@
                          condrepr=('<extra[%r] %r>', label, value))
 
 @predicate('filelog(pattern)', safe=True)
-def filelog(repo, subset, x):
+def filelog(repo, x):
     """Changesets connected to the specified filelog.
 
     For performance reasons, visits only revisions mentioned in the file-level
@@ -873,7 +880,7 @@
                             # deletion in changelog
                             continue
 
-    return subset & s
+    return s
 
 @predicate('first(set, [n])', safe=True, takeorder=True)
 def first(repo, subset, x, order):
@@ -881,7 +888,7 @@
     """
     return limit(repo, subset, x, order)
 
-def _follow(repo, subset, x, name, followfirst=False):
+def _follow(repo, x, name, followfirst=False):
     l = getargs(x, 0, 2, _("%s takes no arguments or a pattern "
                            "and an optional revset") % name)
     c = repo['.']
@@ -909,7 +916,7 @@
     else:
         s = dagop.revancestors(repo, baseset([c.rev()]), followfirst)
 
-    return subset & s
+    return s
 
 @predicate('_flipand(x, y)', safe=True, takeorder=True)
 def _flipand(repo, subset, args, order):
@@ -925,24 +932,24 @@
     return getset(repo, getset(repo, subset, x, xorder), y, order)
 
 @predicate('follow([pattern[, startrev]])', safe=True)
-def follow(repo, subset, x):
+def follow(repo, x):
     """
     An alias for ``::.`` (ancestors of the working directory's first parent).
     If pattern is specified, the histories of files matching given
     pattern in the revision given by startrev are followed, including copies.
     """
-    return _follow(repo, subset, x, 'follow')
+    return _follow(repo, x, 'follow')
 
 @predicate('_followfirst', safe=True)
-def _followfirst(repo, subset, x):
+def _followfirst(repo, x):
     # ``followfirst([pattern[, startrev]])``
     # Like ``follow([pattern[, startrev]])`` but follows only the first parent
     # of every revisions or files revisions.
-    return _follow(repo, subset, x, '_followfirst', followfirst=True)
+    return _follow(repo, x, '_followfirst', followfirst=True)
 
 @predicate('followlines(file, fromline:toline[, startrev=., descend=False])',
            safe=True)
-def followlines(repo, subset, x):
+def followlines(repo, x):
     """Changesets modifying `file` in line range ('fromline', 'toline').
 
     Line range corresponds to 'file' content at 'startrev' and should hence be
@@ -999,15 +1006,15 @@
             (c.rev() for c, _linerange
              in dagop.blockancestors(fctx, fromline, toline)),
             iterasc=False)
-    return subset & rs
+    return rs
 
 @predicate('all()', safe=True)
-def getall(repo, subset, x):
+def getall(repo, x):
     """All changesets, the same as ``0:tip``.
     """
     # i18n: "all" is a keyword
     getargs(x, 0, 0, _("all takes no arguments"))
-    return subset & spanset(repo)  # drop "null" if any
+    return spanset(repo)  # drop "null" if any
 
 @predicate('grep(regex)')
 def grep(repo, subset, x):
@@ -1108,7 +1115,7 @@
     return _matchfiles(repo, subset, ('string', 'p:' + pat))
 
 @predicate('head()', safe=True)
-def head(repo, subset, x):
+def head(repo, x):
     """Changeset is a named branch head.
     """
     # i18n: "head" is a keyword
@@ -1117,7 +1124,7 @@
     cl = repo.changelog
     for ls in repo.branchmap().itervalues():
         hs.update(cl.rev(h) for h in ls)
-    return subset & baseset(hs)
+    return baseset(hs)
 
 @predicate('heads(set)', safe=True)
 def heads(repo, subset, x):
@@ -1128,13 +1135,13 @@
     return s - ps
 
 @predicate('hidden()', safe=True)
-def hidden(repo, subset, x):
+def hidden(repo, x):
     """Hidden changesets.
     """
     # i18n: "hidden" is a keyword
     getargs(x, 0, 0, _("hidden takes no arguments"))
     hiddenrevs = repoview.filterrevs(repo, 'visible')
-    return subset & hiddenrevs
+    return hiddenrevs
 
 @predicate('keyword(string)', safe=True)
 def keyword(repo, subset, x):
@@ -1265,7 +1272,7 @@
     return checkstatus(repo, subset, pat, 0)
 
 @predicate('named(namespace)')
-def named(repo, subset, x):
+def named(repo, x):
     """The changesets in a given namespace.
 
     Pattern matching is supported for `namespace`. See
@@ -1299,7 +1306,7 @@
                 names.update(repo[n].rev() for n in ns.nodes(repo, name))
 
     names -= {node.nullrev}
-    return subset & names
+    return names
 
 @predicate('id(string)', safe=True)
 def node_(repo, subset, x):
@@ -1331,15 +1338,15 @@
     return result & subset
 
 @predicate('obsolete()', safe=True)
-def obsolete(repo, subset, x):
+def obsolete(repo, x):
     """Mutable changeset with a newer version."""
     # i18n: "obsolete" is a keyword
     getargs(x, 0, 0, _("obsolete takes no arguments"))
     obsoletes = obsmod.getrevs(repo, 'obsolete')
-    return subset & obsoletes
+    return obsoletes
 
 @predicate('only(set, [set])', safe=True)
-def only(repo, subset, x):
+def only(repo, x):
     """Changesets that are ancestors of the first set that are not ancestors
     of any other head in the repo. If a second set is specified, the result
     is ancestors of the first set that are not ancestors of the second set
@@ -1360,12 +1367,10 @@
         exclude = getset(repo, fullreposet(repo), args[1])
 
     results = set(cl.findmissingrevs(common=exclude, heads=include))
-    # XXX we should turn this into a baseset instead of a set, smartset may do
-    # some optimizations from the fact this is a baseset.
-    return subset & results
+    return baseset(results)
 
 @predicate('origin([set])', safe=True)
-def origin(repo, subset, x):
+def origin(repo, x):
     """
     Changesets that were specified as a source for the grafts, transplants or
     rebases that created the given revisions.  Omitting the optional set is the
@@ -1392,12 +1397,10 @@
 
     o = {_firstsrc(r) for r in dests}
     o -= {None}
-    # XXX we should turn this into a baseset instead of a set, smartset may do
-    # some optimizations from the fact this is a baseset.
-    return subset & o
+    return baseset(o)
 
 @predicate('outgoing([path])', safe=False)
-def outgoing(repo, subset, x):
+def outgoing(repo, x):
     """Changesets not found in the specified destination repository, or the
     default push location.
     """
@@ -1421,16 +1424,16 @@
     repo.ui.popbuffer()
     cl = repo.changelog
     o = {cl.rev(r) for r in outgoing.missing}
-    return subset & o
+    return o
 
 @predicate('p1([set])', safe=True)
-def p1(repo, subset, x):
+def p1(repo, x):
     """First parent of changesets in set, or the working directory.
     """
     if x is None:
         p = repo[x].p1().rev()
         if p >= 0:
-            return subset & baseset([p])
+            return baseset([p])
         return baseset()
 
     ps = set()
@@ -1441,12 +1444,10 @@
         except error.WdirUnsupported:
             ps.add(repo[r].parents()[0].rev())
     ps -= {node.nullrev}
-    # XXX we should turn this into a baseset instead of a set, smartset may do
-    # some optimizations from the fact this is a baseset.
-    return subset & ps
+    return baseset(ps)
 
 @predicate('p2([set])', safe=True)
-def p2(repo, subset, x):
+def p2(repo, x):
     """Second parent of changesets in set, or the working directory.
     """
     if x is None:
@@ -1454,7 +1455,7 @@
         try:
             p = ps[1].rev()
             if p >= 0:
-                return subset & baseset([p])
+                return baseset([p])
             return baseset()
         except IndexError:
             return baseset()
@@ -1469,12 +1470,10 @@
             if len(parents) == 2:
                 ps.add(parents[1])
     ps -= {node.nullrev}
-    # XXX we should turn this into a baseset instead of a set, smartset may do
-    # some optimizations from the fact this is a baseset.
-    return subset & ps
+    return baseset(ps)
 
 def parentpost(repo, subset, x, order):
-    return p1(repo, subset, x)
+    return intersect(subset, p1(repo, x), order)
 
 @predicate('parents([set])', safe=True, takeorder=True)
 def parents(repo, subset, x, order=anyorder):
@@ -1496,26 +1495,26 @@
     ps -= {node.nullrev}
     return intersect(subset, ps, order)
 
-def _phase(repo, subset, *targets):
+def _phase(repo, *targets):
     """helper to select all rev in <targets> phases"""
     s = repo._phasecache.getrevset(repo, targets)
-    return subset & s
+    return s
 
 @predicate('draft()', safe=True)
-def draft(repo, subset, x):
+def draft(repo, x):
     """Changeset in draft phase."""
     # i18n: "draft" is a keyword
     getargs(x, 0, 0, _("draft takes no arguments"))
     target = phases.draft
-    return _phase(repo, subset, target)
+    return _phase(repo, target)
 
 @predicate('secret()', safe=True)
-def secret(repo, subset, x):
+def secret(repo, x):
     """Changeset in secret phase."""
     # i18n: "secret" is a keyword
     getargs(x, 0, 0, _("secret takes no arguments"))
     target = phases.secret
-    return _phase(repo, subset, target)
+    return _phase(repo, target)
 
 def parentspec(repo, subset, x, n, order):
     """``set^0``
@@ -1566,9 +1565,9 @@
 
 # for internal use
 @predicate('_notpublic', safe=True)
-def _notpublic(repo, subset, x):
+def _notpublic(repo, x):
     getargs(x, 0, 0, "_notpublic takes no arguments")
-    return _phase(repo, subset, phases.draft, phases.secret)
+    return _phase(repo, phases.draft, phases.secret)
 
 @predicate('public()', safe=True)
 def public(repo, subset, x):
@@ -1629,7 +1628,7 @@
     return checkstatus(repo, subset, pat, 2)
 
 @predicate('rev(number)', safe=True)
-def rev(repo, subset, x):
+def rev(repo, x):
     """Revision with the given numeric identifier.
     """
     # i18n: "rev" is a keyword
@@ -1642,7 +1641,7 @@
         raise error.ParseError(_("rev expects a number"))
     if l not in repo.changelog and l not in (node.nullrev, node.wdirrev):
         return baseset()
-    return subset & baseset([l])
+    return baseset([l])
 
 @predicate('matching(revision [, field])', safe=True)
 def matching(repo, subset, x):
@@ -1765,8 +1764,8 @@
         l.reverse()
     return l
 
-@predicate('roots(set)', safe=True)
-def roots(repo, subset, x):
+@predicate('roots(set)', safe=True, takeorder=True)
+def roots(repo, subset, x, order):
     """Changesets in set with no parent changeset in set.
     """
     s = getset(repo, fullreposet(repo), x)
@@ -1776,7 +1775,9 @@
             if 0 <= p and p in s:
                 return False
         return True
-    return subset & s.filter(filter, condrepr='<roots>')
+    if order == defineorder:
+        s.sort()
+    return intersect(subset, s.filter(filter, condrepr='<roots>'), order)
 
 _sortkeyfuncs = {
     'rev': lambda c: c.rev(),
@@ -1935,12 +1936,12 @@
     return smartset.baseset(result - repo.changelog.filteredrevs)
 
 @predicate('successors(set)', safe=True)
-def successors(repo, subset, x):
+def successors(repo, x):
     """All successors for set, including the given set themselves"""
     s = getset(repo, fullreposet(repo), x)
     f = lambda nodes: obsutil.allsuccessors(repo.obsstore, nodes)
     d = _mapbynodefunc(repo, s, f)
-    return subset & d
+    return d
 
 def _substringmatcher(pattern, casesensitive=True):
     kind, pattern, matcher = util.stringmatcher(pattern,
@@ -1954,7 +1955,7 @@
     return kind, pattern, matcher
 
 @predicate('tag([name])', safe=True)
-def tag(repo, subset, x):
+def tag(repo, x):
     """The specified tag by name, or all tagged revisions if no name is given.
 
     Pattern matching is supported for `name`. See
@@ -1979,28 +1980,28 @@
             s = {cl.rev(n) for t, n in repo.tagslist() if matcher(t)}
     else:
         s = {cl.rev(n) for t, n in repo.tagslist() if t != 'tip'}
-    return subset & s
+    return s
 
 @predicate('tagged', safe=True)
-def tagged(repo, subset, x):
-    return tag(repo, subset, x)
+def tagged(repo, x):
+    return tag(repo, x)
 
 @predicate('unstable()', safe=True)
-def unstable(repo, subset, x):
+def unstable(repo, x):
     msg = ("'unstable()' is deprecated, "
            "use 'orphan()'")
     repo.ui.deprecwarn(msg, '4.4')
 
-    return orphan(repo, subset, x)
+    return orphan(repo, x)
 
 @predicate('orphan()', safe=True)
-def orphan(repo, subset, x):
+def orphan(repo, x):
     """Non-obsolete changesets with obsolete ancestors. (EXPERIMENTAL)
     """
     # i18n: "orphan" is a keyword
     getargs(x, 0, 0, _("orphan takes no arguments"))
     orphan = obsmod.getrevs(repo, 'orphan')
-    return subset & orphan
+    return orphan
 
 
 @predicate('user(string)', safe=True)