revset: remove order information from tree (API)

Keeping `order` in tree makes AST operation harder. And there could be
invalid cases if trees could be generated and compounded freely, like:

  SetA(order=define) & SetB(order=define)
                                  ^^^^^^ couldn't be satisfied

This patch changes the code to calculate order on the fly, during tree
traversal. Optimization of reordering `and` arguments is preserved by
introducing a new internal operation `flipand`.

.. api::

   revset.stringset() now takes 'order' as the last argument.

Differential Revision: https://phab.mercurial-scm.org/D451

mercurial/revset.py

@@ -52,10 +52,10 fullreposet = smartset.fullreposet
 
 # helpers
 
-def getset(repo, subset, x):
+def getset(repo, subset, x, order=defineorder):
     if not x:
         raise error.ParseError(_("missing argument"))
-    return methods[x[0]](repo, subset, *x[1:])
+    return methods[x[0]](repo, subset, *x[1:], order=order)
 
 def _getrevsource(repo, r):
     extra = repo[r].extra()
@@ -69,7 +69,7 def _getrevsource(repo, r):
 
 # operator methods
 
-def stringset(repo, subset, x):
+def stringset(repo, subset, x, order):
     x = scmutil.intrev(repo[x])
     if (x in subset
         or x == node.nullrev and isinstance(subset, fullreposet)):
@@ -126,30 +126,42 def dagrange(repo, subset, x, y, order):
     return subset & xs
 
 def andset(repo, subset, x, y, order):
-    return getset(repo, getset(repo, subset, x), y)
+    if order == anyorder:
+        yorder = anyorder
+    else:
+        yorder = followorder
+    return getset(repo, getset(repo, subset, x, order), y, yorder)
+
+def flipandset(repo, subset, y, x, order):
+    # 'flipand(y, x)' is equivalent to 'and(x, y)', but faster when y is small
+    if order == anyorder:
+        yorder = anyorder
+    else:
+        yorder = followorder
+    return getset(repo, getset(repo, subset, y, yorder), x, order)
 
 def differenceset(repo, subset, x, y, order):
-    return getset(repo, subset, x) - getset(repo, subset, y)
+    return getset(repo, subset, x, order) - getset(repo, subset, y, anyorder)
 
-def _orsetlist(repo, subset, xs):
+def _orsetlist(repo, subset, xs, order):
     assert xs
     if len(xs) == 1:
-        return getset(repo, subset, xs[0])
+        return getset(repo, subset, xs[0], order)
     p = len(xs) // 2
-    a = _orsetlist(repo, subset, xs[:p])
-    b = _orsetlist(repo, subset, xs[p:])
+    a = _orsetlist(repo, subset, xs[:p], order)
+    b = _orsetlist(repo, subset, xs[p:], order)
     return a + b
 
 def orset(repo, subset, x, order):
     xs = getlist(x)
     if order == followorder:
         # slow path to take the subset order
-        return subset & _orsetlist(repo, fullreposet(repo), xs)
+        return subset & _orsetlist(repo, fullreposet(repo), xs, anyorder)
     else:
-        return _orsetlist(repo, subset, xs)
+        return _orsetlist(repo, subset, xs, order)
 
 def notset(repo, subset, x, order):
-    return subset - getset(repo, subset, x)
+    return subset - getset(repo, subset, x, anyorder)
 
 def relationset(repo, subset, x, y, order):
     raise error.ParseError(_("can't use a relation in this context"))
@@ -176,11 +188,11 def relsubscriptset(repo, subset, x, y,
 def subscriptset(repo, subset, x, y, order):
     raise error.ParseError(_("can't use a subscript in this context"))
 
-def listset(repo, subset, *xs):
+def listset(repo, subset, *xs, **opts):
     raise error.ParseError(_("can't use a list in this context"),
                            hint=_('see hg help "revsets.x or y"'))
 
-def keyvaluepair(repo, subset, k, v):
+def keyvaluepair(repo, subset, k, v, order):
     raise error.ParseError(_("can't use a key-value pair in this context"))
 
 def func(repo, subset, a, b, order):
@@ -1508,8 +1520,8 def parentspec(repo, subset, x, n, order
                     ps.add(parents[1].rev())
     return subset & ps
 
-@predicate('present(set)', safe=True)
-def present(repo, subset, x):
+@predicate('present(set)', safe=True, takeorder=True)
+def present(repo, subset, x, order):
     """An empty set, if any revision in set isn't found; otherwise,
     all revisions in set.
 
@@ -1518,7 +1530,7 def present(repo, subset, x):
     to continue even in such cases.
     """
     try:
-        return getset(repo, subset, x)
+        return getset(repo, subset, x, order)
     except error.RepoLookupError:
         return baseset()
 
@@ -1718,7 +1730,7 def matching(repo, subset, x):
 def reverse(repo, subset, x, order):
     """Reverse order of set.
     """
-    l = getset(repo, subset, x)
+    l = getset(repo, subset, x, order)
     if order == defineorder:
         l.reverse()
     return l
@@ -1802,7 +1814,7 def sort(repo, subset, x, order):
 
     """
     s, keyflags, opts = _getsortargs(x)
-    revs = getset(repo, subset, s)
+    revs = getset(repo, subset, s, order)
 
     if not keyflags or order != defineorder:
         return revs
@@ -1988,7 +2000,7 def _orderedlist(repo, subset, x):
                 raise ValueError
             revs = [r]
         except ValueError:
-            revs = stringset(repo, subset, t)
+            revs = stringset(repo, subset, t, defineorder)
 
         for r in revs:
             if r in seen:
@@ -2052,6 +2064,7 methods = {
     "string": stringset,
     "symbol": stringset,
     "and": andset,
+    "flipand": flipandset,
     "or": orset,
     "not": notset,
     "difference": differenceset,
@@ -2113,17 +2126,17 def matchany(ui, specs, repo=None, order
     if aliases:
         tree = revsetlang.expandaliases(tree, aliases, warn=warn)
     tree = revsetlang.foldconcat(tree)
-    tree = revsetlang.analyze(tree, order)
+    tree = revsetlang.analyze(tree)
     tree = revsetlang.optimize(tree)
     posttreebuilthook(tree, repo)
-    return makematcher(tree)
+    return makematcher(tree, order)
 
-def makematcher(tree):
+def makematcher(tree, order=defineorder):
     """Create a matcher from an evaluatable tree"""
     def mfunc(repo, subset=None):
         if subset is None:
             subset = fullreposet(repo)
-        return getset(repo, subset, tree)
+        return getset(repo, subset, tree, order)
     return mfunc
 
 def loadpredicate(ui, extname, registrarobj):

mercurial/revsetlang.py

@@ -258,7 +258,7 def _matchnamedfunc(x, funcname):
         return
     return x[2]
 
-# Constants for ordering requirement, used in _analyze():
+# Constants for ordering requirement, used in getset():
 #
 # If 'define', any nested functions and operations can change the ordering of
 # the entries in the set. If 'follow', any nested functions and operations
@@ -282,26 +282,10 def _matchnamedfunc(x, funcname):
 #
 # 'y()' can either enforce its ordering requirement or take the ordering
 # specified by 'x()' because 'not()' doesn't care the order.
-#
-# Transition of ordering requirement:
-#
-# 1. starts with 'define'
-# 2. shifts to 'follow' by 'x & y'
-# 3. changes back to 'define' on function call 'f(x)' or function-like
-#    operation 'x (f) y' because 'f' may have its own ordering requirement
-#    for 'x' and 'y' (e.g. 'first(x)')
-#
 anyorder = 'any'        # don't care the order
 defineorder = 'define'  # should define the order
 followorder = 'follow'  # must follow the current order
 
-# transition table for 'x & y', from the current expression 'x' to 'y'
-_tofolloworder = {
-    anyorder: anyorder,
-    defineorder: followorder,
-    followorder: followorder,
-}
-
 def _matchonly(revs, bases):
     """
     >>> f = lambda *args: _matchonly(*map(parse, args))
@@ -340,76 +324,59 def _fixops(x):
 
     return (op,) + tuple(_fixops(y) for y in x[1:])
 
-def _analyze(x, order):
+def _analyze(x):
     if x is None:
         return x
 
     op = x[0]
     if op == 'minus':
-        return _analyze(('and', x[1], ('not', x[2])), order)
+        return _analyze(('and', x[1], ('not', x[2])))
     elif op == 'only':
         t = ('func', ('symbol', 'only'), ('list', x[1], x[2]))
-        return _analyze(t, order)
+        return _analyze(t)
     elif op == 'onlypost':
-        return _analyze(('func', ('symbol', 'only'), x[1]), order)
+        return _analyze(('func', ('symbol', 'only'), x[1]))
     elif op == 'dagrangepre':
-        return _analyze(('func', ('symbol', 'ancestors'), x[1]), order)
+        return _analyze(('func', ('symbol', 'ancestors'), x[1]))
     elif op == 'dagrangepost':
-        return _analyze(('func', ('symbol', 'descendants'), x[1]), order)
+        return _analyze(('func', ('symbol', 'descendants'), x[1]))
     elif op == 'negate':
         s = getstring(x[1], _("can't negate that"))
-        return _analyze(('string', '-' + s), order)
+        return _analyze(('string', '-' + s))
     elif op in ('string', 'symbol'):
         return x
-    elif op == 'and':
-        ta = _analyze(x[1], order)
-        tb = _analyze(x[2], _tofolloworder[order])
-        return (op, ta, tb, order)
-    elif op == 'or':
-        return (op, _analyze(x[1], order), order)
-    elif op == 'not':
-        return (op, _analyze(x[1], anyorder), order)
     elif op == 'rangeall':
-        return (op, None, order)
-    elif op in ('rangepre', 'rangepost', 'parentpost'):
-        return (op, _analyze(x[1], defineorder), order)
+        return (op, None)
+    elif op in {'or', 'not', 'rangepre', 'rangepost', 'parentpost'}:
+        return (op, _analyze(x[1]))
     elif op == 'group':
-        return _analyze(x[1], order)
-    elif op in ('dagrange', 'range', 'parent', 'ancestor', 'relation',
-                'subscript'):
-        ta = _analyze(x[1], defineorder)
-        tb = _analyze(x[2], defineorder)
-        return (op, ta, tb, order)
+        return _analyze(x[1])
+    elif op in {'and', 'dagrange', 'range', 'parent', 'ancestor', 'relation',
+                'subscript'}:
+        ta = _analyze(x[1])
+        tb = _analyze(x[2])
+        return (op, ta, tb)
     elif op == 'relsubscript':
-        ta = _analyze(x[1], defineorder)
-        tb = _analyze(x[2], defineorder)
-        tc = _analyze(x[3], defineorder)
-        return (op, ta, tb, tc, order)
+        ta = _analyze(x[1])
+        tb = _analyze(x[2])
+        tc = _analyze(x[3])
+        return (op, ta, tb, tc)
     elif op == 'list':
-        return (op,) + tuple(_analyze(y, order) for y in x[1:])
+        return (op,) + tuple(_analyze(y) for y in x[1:])
     elif op == 'keyvalue':
-        return (op, x[1], _analyze(x[2], order))
+        return (op, x[1], _analyze(x[2]))
     elif op == 'func':
-        f = getsymbol(x[1])
-        d = defineorder
-        if f == 'present':
-            # 'present(set)' is known to return the argument set with no
-            # modification, so forward the current order to its argument
-            d = order
-        return (op, x[1], _analyze(x[2], d), order)
+        return (op, x[1], _analyze(x[2]))
     raise ValueError('invalid operator %r' % op)
 
-def analyze(x, order=defineorder):
+def analyze(x):
     """Transform raw parsed tree to evaluatable tree which can be fed to
     optimize() or getset()
 
     All pseudo operations should be mapped to real operations or functions
     defined in methods or symbols table respectively.
-
-    'order' specifies how the current expression 'x' is ordered (see the
-    constants defined above.)
     """
-    return _analyze(x, order)
+    return _analyze(x)
 
 def _optimize(x, small):
     if x is None:
@@ -425,24 +392,21 def _optimize(x, small):
     elif op == 'and':
         wa, ta = _optimize(x[1], True)
         wb, tb = _optimize(x[2], True)
-        order = x[3]
         w = min(wa, wb)
 
         # (::x and not ::y)/(not ::y and ::x) have a fast path
         tm = _matchonly(ta, tb) or _matchonly(tb, ta)
         if tm:
-            return w, ('func', ('symbol', 'only'), tm, order)
+            return w, ('func', ('symbol', 'only'), tm)
 
         if tb is not None and tb[0] == 'not':
-            return wa, ('difference', ta, tb[1], order)
-
+            return wa, ('difference', ta, tb[1])
         if wa > wb:
-            return w, (op, tb, ta, order)
-        return w, (op, ta, tb, order)
+            return w, ('flipand', tb, ta)
+        return w, (op, ta, tb)
     elif op == 'or':
         # fast path for machine-generated expression, that is likely to have
         # lots of trivial revisions: 'a + b + c()' to '_list(a b) + c()'
-        order = x[2]
         ws, ts, ss = [], [], []
         def flushss():
             if not ss:
@@ -451,7 +415,7 def _optimize(x, small):
                 w, t = ss[0]
             else:
                 s = '\0'.join(t[1] for w, t in ss)
-                y = ('func', ('symbol', '_list'), ('string', s), order)
+                y = ('func', ('symbol', '_list'), ('string', s))
                 w, t = _optimize(y, False)
             ws.append(w)
             ts.append(t)
@@ -467,37 +431,31 def _optimize(x, small):
         flushss()
         if len(ts) == 1:
             return ws[0], ts[0] # 'or' operation is fully optimized out
-        return max(ws), (op, ('list',) + tuple(ts), order)
+        return max(ws), (op, ('list',) + tuple(ts))
     elif op == 'not':
         # Optimize not public() to _notpublic() because we have a fast version
         if x[1][:3] == ('func', ('symbol', 'public'), None):
-            order = x[1][3]
-            newsym = ('func', ('symbol', '_notpublic'), None, order)
+            newsym = ('func', ('symbol', '_notpublic'), None)
             o = _optimize(newsym, not small)
             return o[0], o[1]
         else:
             o = _optimize(x[1], not small)
-            order = x[2]
-            return o[0], (op, o[1], order)
+            return o[0], (op, o[1])
     elif op == 'rangeall':
         return smallbonus, x
     elif op in ('rangepre', 'rangepost', 'parentpost'):
         o = _optimize(x[1], small)
-        order = x[2]
-        return o[0], (op, o[1], order)
+        return o[0], (op, o[1])
     elif op in ('dagrange', 'range'):
         wa, ta = _optimize(x[1], small)
         wb, tb = _optimize(x[2], small)
-        order = x[3]
-        return wa + wb, (op, ta, tb, order)
+        return wa + wb, (op, ta, tb)
     elif op in ('parent', 'ancestor', 'relation', 'subscript'):
         w, t = _optimize(x[1], small)
-        order = x[3]
-        return w, (op, t, x[2], order)
+        return w, (op, t, x[2])
     elif op == 'relsubscript':
         w, t = _optimize(x[1], small)
-        order = x[4]
-        return w, (op, t, x[2], x[3], order)
+        return w, (op, t, x[2], x[3])
     elif op == 'list':
         ws, ts = zip(*(_optimize(y, small) for y in x[1:]))
         return sum(ws), (op,) + ts
@@ -522,8 +480,7 def _optimize(x, small):
             w = 10 # assume most sorts look at changelog
         else:
             w = 1
-        order = x[3]
-        return w + wa, (op, x[1], ta, order)
+        return w + wa, (op, x[1], ta)
     raise ValueError('invalid operator %r' % op)
 
 def optimize(tree):

tests/test-revset.t

@@ -166,8 +166,7 trivial
     None)
   * optimized:
   (rangeall
-    None
-    define)
+    None)
   * set:
   <spanset+ 0:10>
   0
@@ -495,8 +494,7 keyword arguments
     ('symbol', 'foo')
     (func
       ('symbol', '_notpublic')
-      None
-      any))
+      None))
   hg: parse error: can't use a key-value pair in this context
   [255]
 
@@ -538,21 +536,16 left-hand side of relation-subscript ope
     (not
       (func
         ('symbol', 'public')
-        None
-        any)
-      define)
+        None))
     ('symbol', 'generations')
-    ('symbol', '0')
-    define)
+    ('symbol', '0'))
   * optimized:
   (relsubscript
     (func
       ('symbol', '_notpublic')
-      None
-      any)
+      None)
     ('symbol', 'generations')
-    ('symbol', '0')
-    define)
+    ('symbol', '0'))
 
 resolution of subscript and relation-subscript ternary operators:
 
@@ -560,8 +553,7 resolution of subscript and relation-sub
   * analyzed:
   (subscript
     ('symbol', 'tip')
-    ('symbol', '0')
-    define)
+    ('symbol', '0'))
   hg: parse error: can't use a subscript in this context
   [255]
 
@@ -570,8 +562,7 resolution of subscript and relation-sub
   (relsubscript
     ('symbol', 'tip')
     ('symbol', 'rel')
-    ('symbol', '0')
-    define)
+    ('symbol', '0'))
   hg: parse error: unknown identifier: rel
   [255]
 
@@ -580,10 +571,8 resolution of subscript and relation-sub
   (subscript
     (relation
       ('symbol', 'tip')
-      ('symbol', 'rel')
-      define)
-    ('symbol', '0')
-    define)
+      ('symbol', 'rel'))
+    ('symbol', '0'))
   hg: parse error: can't use a subscript in this context
   [255]
 
@@ -593,10 +582,8 resolution of subscript and relation-sub
     (relsubscript
       ('symbol', 'tip')
       ('symbol', 'rel')
-      ('symbol', '0')
-      define)
-    ('symbol', '1')
-    define)
+      ('symbol', '0'))
+    ('symbol', '1'))
   hg: parse error: can't use a subscript in this context
   [255]
 
@@ -605,11 +592,9 resolution of subscript and relation-sub
   (relsubscript
     (relation
       ('symbol', 'tip')
-      ('symbol', 'rel0')
-      define)
+      ('symbol', 'rel0'))
     ('symbol', 'rel1')
-    ('symbol', '1')
-    define)
+    ('symbol', '1'))
   hg: parse error: unknown identifier: rel1
   [255]
 
@@ -619,11 +604,9 resolution of subscript and relation-sub
     (relsubscript
       ('symbol', 'tip')
       ('symbol', 'rel0')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     ('symbol', 'rel1')
-    ('symbol', '1')
-    define)
+    ('symbol', '1'))
   hg: parse error: unknown identifier: rel1
   [255]
 
@@ -700,20 +683,15 parsed tree at stages:
     (or
       (list
         ('symbol', '0')
-        ('symbol', '1'))
-      define)
+        ('symbol', '1')))
     (not
-      ('symbol', '1')
-      follow)
-    define)
+      ('symbol', '1')))
   * optimized:
   (difference
     (func
       ('symbol', '_list')
-      ('string', '0\x001')
-      define)
-    ('symbol', '1')
-    define)
+      ('string', '0\x001'))
+    ('symbol', '1'))
   0
 
   $ hg debugrevspec -p unknown '0'
@@ -733,18 +711,14 verify optimized tree:
   (and
     (func
       ('symbol', 'r3232')
-      None
-      define)
-    ('symbol', '2')
-    define)
+      None)
+    ('symbol', '2'))
   * optimized:
-  (and
+  (flipand
     ('symbol', '2')
     (func
       ('symbol', 'r3232')
-      None
-      define)
-    define)
+      None))
   * analyzed set:
   <baseset [2]>
   * optimized set:
@@ -776,8 +750,7 may be hidden (issue5385)
     None)
   * analyzed:
   (rangeall
-    None
-    define)
+    None)
   * set:
   <spanset+ 0:10>
   0
@@ -793,8 +766,7 may be hidden (issue5385)
   $ try -p analyzed ':1'
   * analyzed:
   (rangepre
-    ('symbol', '1')
-    define)
+    ('symbol', '1'))
   * set:
   <spanset+ 0:2>
   0
@@ -805,9 +777,7 may be hidden (issue5385)
     (or
       (list
         ('symbol', '1')
-        ('symbol', '2'))
-      define)
-    define)
+        ('symbol', '2'))))
   * set:
   <spanset+ 0:3>
   0
@@ -818,9 +788,7 may be hidden (issue5385)
   (rangepre
     (and
       ('symbol', '1')
-      ('symbol', '2')
-      define)
-    define)
+      ('symbol', '2')))
   * set:
   <baseset []>
 
@@ -1643,11 +1611,8 Test operand of '%' is optimized recursi
     (difference
       (range
         ('symbol', '8')
-        ('symbol', '9')
-        define)
-      ('symbol', '8')
-      define)
-    define)
+        ('symbol', '9'))
+      ('symbol', '8')))
   * set:
   <baseset+ [8, 9]>
   8
@@ -1663,8 +1628,7 Test operand of '%' is optimized recursi
     ('symbol', 'only')
     (list
       ('symbol', '9')
-      ('symbol', '5'))
-    define)
+      ('symbol', '5')))
   * set:
   <baseset+ [2, 4, 8, 9]>
   2
@@ -1999,18 +1963,13 ordering defined by it.
     (and
       (range
         ('symbol', '3')
-        ('symbol', '0')
-        define)
+        ('symbol', '0'))
       (range
         ('symbol', '0')
-        ('symbol', '3')
-        follow)
-      define)
+        ('symbol', '3')))
     (range
       ('symbol', '2')
-      ('symbol', '1')
-      any)
-    define)
+      ('symbol', '1')))
   * set:
   <filteredset
     <filteredset
@@ -2039,13 +1998,10 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', '_list')
-      ('string', '0\x001\x002')
-      follow)
-    define)
+      ('string', '0\x001\x002')))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2072,17 +2028,13 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (or
       (list
         (range
           ('symbol', '0')
-          ('symbol', '1')
-          follow)
-        ('symbol', '2'))
-      follow)
-    define)
+          ('symbol', '1'))
+        ('symbol', '2'))))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2104,16 +2056,13 ordering defined by it.
       ('symbol', '_intlist')
       ('string', '0\x001\x002')))
   * optimized:
-  (and
+  (flipand
     (func
       ('symbol', '_intlist')
-      ('string', '0\x001\x002')
-      follow)
+      ('string', '0\x001\x002'))
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
-    define)
+      ('symbol', '0')))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2134,13 +2083,10 ordering defined by it.
   (and
     (func
       ('symbol', '_intlist')
-      ('string', '0\x002\x001')
-      define)
+      ('string', '0\x002\x001'))
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      follow)
-    define)
+      ('symbol', '0')))
   * set:
   <filteredset
     <baseset [0, 2, 1]>,
@@ -2163,13 +2109,10 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', '_hexlist')
-      ('string', '*') (glob)
-      follow)
-    define)
+      ('string', '*'))) (glob)
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2187,16 +2130,13 ordering defined by it.
       ('symbol', '2')
       ('symbol', '0')))
   * optimized:
-  (and
+  (flipand
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      follow)
+      ('symbol', '0'))
     (func
       ('symbol', '_hexlist')
-      ('string', '*') (glob)
-      define)
-    define)
+      ('string', '*'))) (glob)
   * set:
   <baseset [0, 2, 1]>
   0
@@ -2211,13 +2151,10 ordering defined by it.
   (difference
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', '_list')
-      ('string', '0\x001')
-      any)
-    define)
+      ('string', '0\x001')))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2230,19 +2167,14 ordering defined by it.
   (difference
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (and
       (range
         ('symbol', '0')
-        ('symbol', '2')
-        any)
+        ('symbol', '2'))
       (func
         ('symbol', '_list')
-        ('string', '0\x001')
-        any)
-      any)
-    define)
+        ('string', '0\x001'))))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2259,9 +2191,7 ordering defined by it.
     ('symbol', 'present')
     (func
       ('symbol', '_list')
-      ('string', '2\x000\x001')
-      define)
-    define)
+      ('string', '2\x000\x001')))
   * set:
   <baseset [2, 0, 1]>
   2
@@ -2284,16 +2214,12 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', 'present')
       (func
         ('symbol', '_list')
-        ('string', '0\x001\x002')
-        follow)
-      follow)
-    define)
+        ('string', '0\x001\x002'))))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2318,16 +2244,12 ordering defined by it.
   (and
     (range
       ('symbol', '0')
-      ('symbol', '2')
-      define)
+      ('symbol', '2'))
     (func
       ('symbol', 'reverse')
       (func
         ('symbol', 'all')
-        None
-        define)
-      follow)
-    define)
+        None)))
   * set:
   <filteredset
     <spanset+ 0:3>,
@@ -2355,18 +2277,14 ordering defined by it.
   (and
     (range
       ('symbol', '0')
-      ('symbol', '2')
-      define)
+      ('symbol', '2'))
     (func
       ('symbol', 'sort')
       (list
         (func
           ('symbol', 'all')
-          None
-          define)
-        ('string', '-rev'))
-      follow)
-    define)
+          None)
+        ('string', '-rev'))))
   * set:
   <filteredset
     <spanset+ 0:3>,
@@ -2402,16 +2320,12 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', 'first')
       (func
         ('symbol', '_list')
-        ('string', '1\x000\x002')
-        define)
-      follow)
-    define)
+        ('string', '1\x000\x002'))))
   * set:
   <filteredset
     <baseset [1]>,
@@ -2435,16 +2349,12 ordering defined by it.
   (difference
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (func
       ('symbol', 'last')
       (func
         ('symbol', '_list')
-        ('string', '0\x002\x001')
-        define)
-      any)
-    define)
+        ('string', '0\x002\x001'))))
   * set:
   <filteredset
     <spanset- 0:3>,
@@ -2477,29 +2387,21 ordering defined by it.
   (and
     (range
       ('symbol', '2')
-      ('symbol', '0')
-      define)
+      ('symbol', '0'))
     (range
       (func
         ('symbol', '_list')
-        ('string', '1\x000\x002')
-        define)
+        ('string', '1\x000\x002'))
       (func
         ('symbol', '_list')
-        ('string', '0\x002\x001')
-        define)
-      follow)
-    define)
+        ('string', '0\x002\x001'))))
   * set:
   <filteredset
     <spanset- 0:3>,
     <baseset [1]>>
   1
 
- 'A & B' can be rewritten as 'B & A' by weight, but that's fine as long as
- the ordering rule is determined before the rewrite; in this example,
- 'B' follows the order of the initial set, which is the same order as 'A'
- since 'A' also follows the order:
+ 'A & B' can be rewritten as 'flipand(B, A)' by weight.
 
   $ try --optimize 'contains("glob:*") & (2 + 0 + 1)'
   (and
@@ -2513,16 +2415,13 ordering defined by it.
           ('symbol', '0')
           ('symbol', '1')))))
   * optimized:
-  (and
+  (flipand
     (func
       ('symbol', '_list')
-      ('string', '2\x000\x001')
-      follow)
+      ('string', '2\x000\x001'))
     (func
       ('symbol', 'contains')
-      ('string', 'glob:*')
-      define)
-    define)
+      ('string', 'glob:*')))
   * set:
   <filteredset
     <baseset+ [0, 1, 2]>,
@@ -2548,19 +2447,15 ordering defined by it.
           ('symbol', '2')
           ('symbol', '1')))))
   * optimized:
-  (and
+  (flipand
     (func
       ('symbol', '_list')
-      ('string', '0\x002\x001')
-      follow)
+      ('string', '0\x002\x001'))
     (func
       ('symbol', 'reverse')
       (func
         ('symbol', 'contains')
-        ('string', 'glob:*')
-        define)
-      define)
-    define)
+        ('string', 'glob:*'))))
   * set:
   <filteredset
     <baseset- [0, 1, 2]>,
@@ -2953,8 +2848,7 test optimization of trivial `or` operat
   * optimized:
   (func
     ('symbol', '_list')
-    ('string', '0\x001\x002\x00-2\x00tip\x00null')
-    define)
+    ('string', '0\x001\x002\x00-2\x00tip\x00null'))
   * set:
   <baseset [0, 1, 2, 8, 9, -1]>
   0
@@ -2977,13 +2871,10 test optimization of trivial `or` operat
     (list
       (func
         ('symbol', '_list')
-        ('string', '0\x001')
-        define)
+        ('string', '0\x001'))
       (range
         ('symbol', '2')
-        ('symbol', '3')
-        define))
-    define)
+        ('symbol', '3'))))
   * set:
   <addset
     <baseset [0, 1]>,
@@ -3010,18 +2901,14 test optimization of trivial `or` operat
     (list
       (range
         ('symbol', '0')
-        ('symbol', '1')
-        define)
+        ('symbol', '1'))
       ('symbol', '2')
       (range
         ('symbol', '3')
-        ('symbol', '4')
-        define)
+        ('symbol', '4'))
       (func
         ('symbol', '_list')
-        ('string', '5\x006')
-        define))
-    define)
+        ('string', '5\x006'))))
   * set:
   <addset
     <addset
@@ -3048,8 +2935,7 unoptimized `or` looks like this
       ('symbol', '1')
       ('symbol', '2')
       ('symbol', '3')
-      ('symbol', '4'))
-    define)
+      ('symbol', '4')))
   * set:
   <addset
     <addset
@@ -3169,8 +3055,7 no crash by empty group "()" while optim
   (or
     (list
       ('symbol', '0')
-      None)
-    define)
+      None))
   hg: parse error: missing argument
   [255]
 
@@ -3200,8 +3085,7 check that conversion to only works
     ('symbol', 'only')
     (list
       ('symbol', '3')
-      ('symbol', '1'))
-    define)
+      ('symbol', '1')))
   * set:
   <baseset+ [3]>
   3
@@ -3218,8 +3102,7 check that conversion to only works
     ('symbol', 'only')
     (list
       ('symbol', '1')
-      ('symbol', '3'))
-    define)
+      ('symbol', '3')))
   * set:
   <baseset+ []>
   $ try --optimize 'not ::2 and ::6'
@@ -3234,8 +3117,7 check that conversion to only works
     ('symbol', 'only')
     (list
       ('symbol', '6')
-      ('symbol', '2'))
-    define)
+      ('symbol', '2')))
   * set:
   <baseset+ [3, 4, 5, 6]>
   3
@@ -3256,8 +3138,7 check that conversion to only works
     ('symbol', 'only')
     (list
       ('symbol', '6')
-      ('symbol', '4'))
-    define)
+      ('symbol', '4')))
   * set:
   <baseset+ [3, 5, 6]>
   3
@@ -3273,13 +3154,11 no crash by empty group "()" while optim
     (group
       None))
   * optimized:
-  (and
+  (flipand
     None
     (func
       ('symbol', 'ancestors')
-      ('symbol', '1')
-      define)
-    define)
+      ('symbol', '1')))
   hg: parse error: missing argument
   [255]
 
@@ -3290,15 +3169,12 optimization to only() works only if anc
   (difference
     (func
       ('symbol', 'ancestors')
-      ('symbol', '6')
-      define)
+      ('symbol', '6'))
     (func
       ('symbol', 'ancestors')
       (list
         ('symbol', '4')
-        ('symbol', '1'))
-      any)
-    define)
+        ('symbol', '1'))))
   0
   1
   3
@@ -3311,13 +3187,10 optimization to only() works only if anc
       ('symbol', 'ancestors')
       (list
         ('symbol', '6')
-        ('symbol', '1'))
-      define)
+        ('symbol', '1')))
     (func
       ('symbol', 'ancestors')
-      ('symbol', '4')
-      any)
-    define)
+      ('symbol', '4')))
   5
   6
 
@@ -3331,15 +3204,12 to support it)
       ('symbol', 'ancestors')
       (keyvalue
         ('symbol', 'set')
-        ('symbol', '6'))
-      define)
+        ('symbol', '6')))
     (func
       ('symbol', 'ancestors')
       (keyvalue
         ('symbol', 'set')
-        ('symbol', '4'))
-      any)
-    define)
+        ('symbol', '4'))))
   3
   5
   6