Patchwork [1,of,7] revset: wrap arguments of 'or' by 'list' node

Submitter Yuya Nishihara Sept. 13, 2016, 4:13 p.m. mbox | patch /patch/16601/ Accepted show

Yuya Nishihara - Sept. 13, 2016, 4:13 p.m.
```# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1470557045 -32400
#      Sun Aug 07 17:04:05 2016 +0900
# Node ID b823d0d738ff6032f58e67ef183fe7e0deee1cf4
# Parent  be16091ac14d03f3cc038b2fb26efe46f785f8d7
revset: wrap arguments of 'or' by 'list' node

This makes the number of 'or' arguments deterministic so we can attach
additional ordering flag to all operator nodes. See the next patch.

We rewrite the tree immediately after chained 'or' operations are flattened
by simplifyinfixops(), so we don't need to care if arguments are stored in
x[1] or x[1:].
```

Patch

```diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -397,15 +397,18 @@  def andset(repo, subset, x, y):
def differenceset(repo, subset, x, y):
return getset(repo, subset, x) - getset(repo, subset, y)

-def orset(repo, subset, *xs):
+def _orsetlist(repo, subset, xs):
assert xs
if len(xs) == 1:
return getset(repo, subset, xs[0])
p = len(xs) // 2
-    a = orset(repo, subset, *xs[:p])
-    b = orset(repo, subset, *xs[p:])
+    a = _orsetlist(repo, subset, xs[:p])
+    b = _orsetlist(repo, subset, xs[p:])
return a + b

+def orset(repo, subset, x):
+    return _orsetlist(repo, subset, getlist(x))
+
def notset(repo, subset, x):
return subset - getset(repo, subset, x)

@@ -2339,6 +2342,10 @@  def _fixops(x):
return _fixops(('range', post, x[2][1]))
elif x[2][0] == 'rangeall':
return _fixops(('rangepost', post))
+    elif op == 'or':
+        # make number of arguments deterministic:
+        # x + y + z -> (or x y z) -> (or (list x y z))
+        return (op, _fixops(('list',) + x[1:]))

return (op,) + tuple(_fixops(y) for y in x[1:])

@@ -2374,7 +2381,7 @@  def _analyze(x):
tb = _analyze(x[2])
return (op, ta, tb)
elif op == 'or':
-        return (op,) + tuple(_analyze(y) for y in x[1:])
+        return (op, _analyze(x[1]))
elif op == 'not':
return (op, _analyze(x[1]))
elif op == 'parentpost':
@@ -2445,7 +2452,7 @@  def _optimize(x, small):
ws.append(w)
ts.append(t)
del ss[:]
-        for y in x[1:]:
+        for y in getlist(x[1]):
w, t = _optimize(y, False)
if t is not None and (t[0] == 'string' or t[0] == 'symbol'):
ss.append((w, t))
@@ -2459,7 +2466,7 @@  def _optimize(x, small):
# we can't reorder trees by weight because it would change the order.
# ("sort(a + b)" == "sort(b + a)", but "a + b" != "b + a")
#   ts = tuple(t for w, t in sorted(zip(ws, ts), key=lambda wt: wt[0]))
-        return max(ws), (op,) + tuple(ts)
+        return max(ws), (op, ('list',) + tuple(ts))
elif op == 'not':
# Optimize not public() to _notpublic() because we have a fast version
if x[1] == ('func', ('symbol', 'public'), None):
@@ -2613,7 +2620,7 @@  def matchany(ui, specs, repo=None):
if len(specs) == 1:
tree = parse(specs[0], lookup)
else:
-        tree = ('or',) + tuple(parse(s, lookup) for s in specs)
+        tree = ('or', ('list',) + tuple(parse(s, lookup) for s in specs))

if ui:
tree = expandaliases(ui, tree)
diff --git a/tests/test-glog.t b/tests/test-glog.t
--- a/tests/test-glog.t
+++ b/tests/test-glog.t
@@ -1455,12 +1455,13 @@  glog always reorders nodes which explain
(group
(group
(or
-        (func
-          ('symbol', 'user')
-          ('string', 'test'))
-        (func
-          ('symbol', 'user')
-          ('string', 'not-a-user')))))
+        (list
+          (func
+            ('symbol', 'user')
+            ('string', 'test'))
+          (func
+            ('symbol', 'user')
+            ('string', 'not-a-user'))))))
\$ testlog -b not-a-branch
abort: unknown revision 'not-a-branch'!
abort: unknown revision 'not-a-branch'!
@@ -1470,26 +1471,28 @@  glog always reorders nodes which explain
(group
(group
(or
-        (func
-          ('symbol', 'branch')
-          ('string', 'default'))
-        (func
-          ('symbol', 'branch')
-          ('string', 'branch'))
-        (func
-          ('symbol', 'branch')
-          ('string', 'branch')))))
+        (list
+          (func
+            ('symbol', 'branch')
+            ('string', 'default'))
+          (func
+            ('symbol', 'branch')
+            ('string', 'branch'))
+          (func
+            ('symbol', 'branch')
+            ('string', 'branch'))))))
\$ testlog -k expand -k merge
[]
(group
(group
(or
-        (func
-          ('symbol', 'keyword')
-          ('string', 'expand'))
-        (func
-          ('symbol', 'keyword')
-          ('string', 'merge')))))
+        (list
+          (func
+            ('symbol', 'keyword')
+            ('string', 'expand'))
+          (func
+            ('symbol', 'keyword')
+            ('string', 'merge'))))))
\$ testlog --only-merges
[]
(group
@@ -1520,17 +1523,19 @@  glog always reorders nodes which explain
(not
(group
(or
-              ('string', '31')
-              (func
-                ('symbol', 'ancestors')
-                ('string', '31')))))
+              (list
+                ('string', '31')
+                (func
+                  ('symbol', 'ancestors')
+                  ('string', '31'))))))
(not
(group
(or
-              ('string', '32')
-              (func
-                ('symbol', 'ancestors')
-                ('string', '32'))))))))
+              (list
+                ('string', '32')
+                (func
+                  ('symbol', 'ancestors')
+                  ('string', '32')))))))))

Dedicated repo for --follow and paths filtering. The g is crafted to
have 2 filelog topological heads in a linear changeset graph.
@@ -1587,12 +1592,13 @@  have 2 filelog topological heads in a li
(group
(group
(or
-        (func
-          ('symbol', 'filelog')
-          ('string', 'a'))
-        (func
-          ('symbol', 'filelog')
-          ('string', 'b')))))
+        (list
+          (func
+            ('symbol', 'filelog')
+            ('string', 'a'))
+          (func
+            ('symbol', 'filelog')
+            ('string', 'b'))))))

Test falling back to slow path for non-existing files

@@ -1744,12 +1750,13 @@  Test --follow and multiple files
(group
(group
(or
-        (func
-          ('symbol', 'follow')
-          ('string', 'g'))
-        (func
-          ('symbol', 'follow')
-          ('string', 'e')))))
+        (list
+          (func
+            ('symbol', 'follow')
+            ('string', 'g'))
+          (func
+            ('symbol', 'follow')
+            ('string', 'e'))))))
\$ cat log.nodes
nodetag 4
nodetag 3
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -187,9 +187,10 @@  trivial
6
\$ try '0|1|2'
(or
-    ('symbol', '0')
-    ('symbol', '1')
-    ('symbol', '2'))
+    (list
+      ('symbol', '0')
+      ('symbol', '1')
+      ('symbol', '2')))
* set:
<baseset [0, 1, 2]>
0
@@ -339,10 +340,11 @@  quoting needed
\$ log '1&2'
\$ try '1&2|3' # precedence - and is higher
(or
-    (and
-      ('symbol', '1')
-      ('symbol', '2'))
-    ('symbol', '3'))
+    (list
+      (and
+        ('symbol', '1')
+        ('symbol', '2'))
+      ('symbol', '3')))
* set:
<baseset []>,
@@ -350,10 +352,11 @@  quoting needed
3
\$ try '1|2&3'
(or
-    ('symbol', '1')
-    (and
-      ('symbol', '2')
-      ('symbol', '3')))
+    (list
+      ('symbol', '1')
+      (and
+        ('symbol', '2')
+        ('symbol', '3'))))
* set:
<baseset [1]>,
@@ -369,11 +372,13 @@  quoting needed
<baseset []>
\$ try '1|(2|3)'
(or
-    ('symbol', '1')
-    (group
-      (or
-        ('symbol', '2')
-        ('symbol', '3'))))
+    (list
+      ('symbol', '1')
+      (group
+        (or
+          (list
+            ('symbol', '2')
+            ('symbol', '3'))))))
* set:
<baseset [1]>,
@@ -465,8 +470,9 @@  keyword arguments
(keyvalue
('symbol', 'foo')
(or
-      ('symbol', 'bar')
-      ('symbol', 'baz')))
+      (list
+        ('symbol', 'bar')
+        ('symbol', 'baz'))))
hg: parse error: can't use a key-value pair in this context
[255]

@@ -528,14 +534,16 @@  parsed tree at stages:
(minus
(group
(or
-        ('symbol', '0')
-        ('symbol', '1')))
+        (list
+          ('symbol', '0')
+          ('symbol', '1'))))
('symbol', '1'))
* analyzed:
(and
(or
-      ('symbol', '0')
-      ('symbol', '1'))
+      (list
+        ('symbol', '0')
+        ('symbol', '1')))
(not
('symbol', '1')))
* optimized:
@@ -1242,9 +1250,10 @@  ordering defined by it.
('symbol', '0'))
(group
(or
-        ('symbol', '0')
-        ('symbol', '1')
-        ('symbol', '2'))))
+        (list
+          ('symbol', '0')
+          ('symbol', '1')
+          ('symbol', '2')))))
* optimized:
(and
(range
@@ -1269,20 +1278,22 @@  ordering defined by it.
('symbol', '0'))
(group
(or
-        (range
-          ('symbol', '0')
-          ('symbol', '1'))
-        ('symbol', '2'))))
+        (list
+          (range
+            ('symbol', '0')
+            ('symbol', '1'))
+          ('symbol', '2')))))
* optimized:
(and
(range
('symbol', '2')
('symbol', '0'))
(or
-      (range
-        ('symbol', '0')
-        ('symbol', '1'))
-      ('symbol', '2')))
+      (list
+        (range
+          ('symbol', '0')
+          ('symbol', '1'))
+        ('symbol', '2'))))
* set:
<filteredset
@@ -1402,9 +1413,10 @@  ordering defined by it.
(func
('symbol', 'present')
(or
-        ('symbol', '0')
-        ('symbol', '1')
-        ('symbol', '2'))))
+        (list
+          ('symbol', '0')
+          ('symbol', '1')
+          ('symbol', '2')))))
* optimized:
(and
(range
@@ -1499,9 +1511,10 @@  ordering defined by it.
(func
('symbol', 'first')
(or
-        ('symbol', '1')
-        ('symbol', '0')
-        ('symbol', '2'))))
+        (list
+          ('symbol', '1')
+          ('symbol', '0')
+          ('symbol', '2')))))
* optimized:
(and
(range
@@ -1528,9 +1541,10 @@  ordering defined by it.
(func
('symbol', 'last')
(or
-          ('symbol', '0')
-          ('symbol', '2')
-          ('symbol', '1')))))
+          (list
+            ('symbol', '0')
+            ('symbol', '2')
+            ('symbol', '1'))))))
* optimized:
(difference
(range
@@ -1562,14 +1576,16 @@  ordering defined by it.
(range
(group
(or
-          ('symbol', '1')
-          ('symbol', '0')
-          ('symbol', '2')))
+          (list
+            ('symbol', '1')
+            ('symbol', '0')
+            ('symbol', '2'))))
(group
(or
-          ('symbol', '0')
-          ('symbol', '2')
-          ('symbol', '1')))))
+          (list
+            ('symbol', '0')
+            ('symbol', '2')
+            ('symbol', '1'))))))
* optimized:
(and
(range
@@ -1599,9 +1615,10 @@  ordering defined by it.
('string', 'glob:*'))
(group
(or
-        ('symbol', '2')
-        ('symbol', '0')
-        ('symbol', '1'))))
+        (list
+          ('symbol', '2')
+          ('symbol', '0')
+          ('symbol', '1')))))
* optimized:
(and
(func
@@ -1628,9 +1645,10 @@  ordering defined by it.
('string', 'glob:*')))
(group
(or
-        ('symbol', '0')
-        ('symbol', '2')
-        ('symbol', '1'))))
+        (list
+          ('symbol', '0')
+          ('symbol', '2')
+          ('symbol', '1')))))
* optimized:
(and
(func
@@ -1975,14 +1993,15 @@  test that `or` operation skips duplicate

\$ try 'reverse(1::5) or ancestors(4)'
(or
-    (func
-      ('symbol', 'reverse')
-      (dagrange
-        ('symbol', '1')
-        ('symbol', '5')))
-    (func
-      ('symbol', 'ancestors')
-      ('symbol', '4')))
+    (list
+      (func
+        ('symbol', 'reverse')
+        (dagrange
+          ('symbol', '1')
+          ('symbol', '5')))
+      (func
+        ('symbol', 'ancestors')
+        ('symbol', '4'))))
* set:
<baseset- [1, 3, 5]>,
@@ -1997,14 +2016,15 @@  test that `or` operation skips duplicate
(func
('symbol', 'sort')
(or
-      (func
-        ('symbol', 'ancestors')
-        ('symbol', '4'))
-      (func
-        ('symbol', 'reverse')
-        (dagrange
-          ('symbol', '1')
-          ('symbol', '5')))))
+      (list
+        (func
+          ('symbol', 'ancestors')
+          ('symbol', '4'))
+        (func
+          ('symbol', 'reverse')
+          (dagrange
+            ('symbol', '1')
+            ('symbol', '5'))))))
* set:
<generatorset+>,
@@ -2020,14 +2040,15 @@  test optimization of trivial `or` operat

\$ try --optimize '0|(1)|"2"|-2|tip|null'
(or
-    ('symbol', '0')
-    (group
-      ('symbol', '1'))
-    ('string', '2')
-    (negate
-      ('symbol', '2'))
-    ('symbol', 'tip')
-    ('symbol', 'null'))
+    (list
+      ('symbol', '0')
+      (group
+        ('symbol', '1'))
+      ('string', '2')
+      (negate
+        ('symbol', '2'))
+      ('symbol', 'tip')
+      ('symbol', 'null')))
* optimized:
(func
('symbol', '_list')
@@ -2043,19 +2064,21 @@  test optimization of trivial `or` operat

\$ try --optimize '0|1|2:3'
(or
-    ('symbol', '0')
-    ('symbol', '1')
-    (range
-      ('symbol', '2')
-      ('symbol', '3')))
+    (list
+      ('symbol', '0')
+      ('symbol', '1')
+      (range
+        ('symbol', '2')
+        ('symbol', '3'))))
* optimized:
(or
-    (func
-      ('symbol', '_list')
-      ('string', '0\x001'))
-    (range
-      ('symbol', '2')
-      ('symbol', '3')))
+    (list
+      (func
+        ('symbol', '_list')
+        ('string', '0\x001'))
+      (range
+        ('symbol', '2')
+        ('symbol', '3'))))
* set:
<baseset [0, 1]>,
@@ -2067,27 +2090,29 @@  test optimization of trivial `or` operat

\$ try --optimize '0:1|2|3:4|5|6'
(or
-    (range
-      ('symbol', '0')
-      ('symbol', '1'))
-    ('symbol', '2')
-    (range
-      ('symbol', '3')
-      ('symbol', '4'))
-    ('symbol', '5')
-    ('symbol', '6'))
+    (list
+      (range
+        ('symbol', '0')
+        ('symbol', '1'))
+      ('symbol', '2')
+      (range
+        ('symbol', '3')
+        ('symbol', '4'))
+      ('symbol', '5')
+      ('symbol', '6')))
* optimized:
(or
-    (range
-      ('symbol', '0')
-      ('symbol', '1'))
-    ('symbol', '2')
-    (range
-      ('symbol', '3')
-      ('symbol', '4'))
-    (func
-      ('symbol', '_list')
-      ('string', '5\x006')))
+    (list
+      (range
+        ('symbol', '0')
+        ('symbol', '1'))
+      ('symbol', '2')
+      (range
+        ('symbol', '3')
+        ('symbol', '4'))
+      (func
+        ('symbol', '_list')
+        ('string', '5\x006'))))
* set:
@@ -2109,11 +2134,12 @@  unoptimized `or` looks like this
\$ try --no-optimized -p analyzed '0|1|2|3|4'
* analyzed:
(or
-    ('symbol', '0')
-    ('symbol', '1')
-    ('symbol', '2')
-    ('symbol', '3')
-    ('symbol', '4'))
+    (list
+      ('symbol', '0')
+      ('symbol', '1')
+      ('symbol', '2')
+      ('symbol', '3')
+      ('symbol', '4')))
* set:
@@ -2188,21 +2214,22 @@  test that chained `or` operations make b

\$ try '0:1|1:2|2:3|3:4|4:5'
(or
-    (range
-      ('symbol', '0')
-      ('symbol', '1'))
-    (range
-      ('symbol', '1')
-      ('symbol', '2'))
-    (range
-      ('symbol', '2')
-      ('symbol', '3'))
-    (range
-      ('symbol', '3')
-      ('symbol', '4'))
-    (range
-      ('symbol', '4')
-      ('symbol', '5')))
+    (list
+      (range
+        ('symbol', '0')
+        ('symbol', '1'))
+      (range
+        ('symbol', '1')
+        ('symbol', '2'))
+      (range
+        ('symbol', '2')
+        ('symbol', '3'))
+      (range
+        ('symbol', '3')
+        ('symbol', '4'))
+      (range
+        ('symbol', '4')
+        ('symbol', '5'))))
* set:
@@ -2224,13 +2251,15 @@  no crash by empty group "()" while optim

\$ try --optimize '0|()'
(or
-    ('symbol', '0')
-    (group
-      None))
+    (list
+      ('symbol', '0')
+      (group
+        None)))
* optimized:
(or
-    ('symbol', '0')
-    None)
+    (list
+      ('symbol', '0')
+      None))
hg: parse error: missing argument
[255]

@@ -2715,10 +2744,12 @@  test infinite recursion
('symbol', '3')))
* expanded:
(or
-    ('symbol', '3')
-    (or
-      ('symbol', '1')
-      ('symbol', '2')))
+    (list
+      ('symbol', '3')
+      (or
+        (list
+          ('symbol', '1')
+          ('symbol', '2')))))
* set:
<baseset [3]>,
@@ -2769,15 +2800,16 @@  test chained `or` operations are flatten
('symbol', '3'))))
* expanded:
(or
-    (range
-      ('symbol', '0')
-      ('symbol', '1'))
-    (range
-      ('symbol', '1')
-      ('symbol', '2'))
-    (range
-      ('symbol', '2')
-      ('symbol', '3')))
+    (list
+      (range
+        ('symbol', '0')
+        ('symbol', '1'))
+      (range
+        ('symbol', '1')
+        ('symbol', '2'))
+      (range
+        ('symbol', '2')
+        ('symbol', '3'))))
* set:
<spanset+ 0:1>,
@@ -2868,10 +2900,11 @@  test unknown reference:
('symbol', 'tip')))
* expanded:
(or
-    ('symbol', 'tip')
-    (func
-      ('symbol', 'desc')
-      ('string', '\$1')))
+    (list
+      ('symbol', 'tip')
+      (func
+        ('symbol', 'desc')
+        ('string', '\$1'))))
* set:
<baseset [9]>,
@@ -2907,8 +2940,9 @@  test unknown reference:
('symbol', 'rs')
(list
(or
-        ('symbol', '2')
-        ('symbol', '3'))
+        (list
+          ('symbol', '2')
+          ('symbol', '3')))
('symbol', 'date')))
* expanded:
(func
@@ -2917,8 +2951,9 @@  test unknown reference:
('symbol', 'sort')
(list
(or
-          ('symbol', '2')
-          ('symbol', '3'))
+          (list
+            ('symbol', '2')
+            ('symbol', '3')))
('symbol', 'date'))))
* set:
<baseset [3, 2]>
@@ -2950,8 +2985,9 @@  test unknown reference:
('symbol', 'rs4')
(list
(or
-        ('symbol', '2')
-        ('symbol', '3'))
+        (list
+          ('symbol', '2')
+          ('symbol', '3')))
('symbol', 'x')
('symbol', 'x')
('symbol', 'date')))
@@ -2962,8 +2998,9 @@  test unknown reference:
('symbol', 'sort')
(list
(or
-          ('symbol', '2')
-          ('symbol', '3'))
+          (list
+            ('symbol', '2')
+            ('symbol', '3')))
('symbol', 'date'))))
* set:
<baseset [3, 2]>
@@ -3034,9 +3071,10 @@  issue2549 - correct optimizations
('symbol', 'limit')
(list
(or
-          ('symbol', '1')
-          ('symbol', '2')
-          ('symbol', '3'))
+          (list
+            ('symbol', '1')
+            ('symbol', '2')
+            ('symbol', '3')))
('symbol', '2')))
(not
('symbol', '2')))
@@ -3054,8 +3092,9 @@  issue2549 - correct optimizations
(func
('symbol', 'max')
(or
-        ('symbol', '1')
-        ('symbol', '2')))
+        (list
+          ('symbol', '1')
+          ('symbol', '2'))))
(not
('symbol', '2')))
* set:
@@ -3071,8 +3110,9 @@  issue2549 - correct optimizations
(func
('symbol', 'min')
(or
-        ('symbol', '1')
-        ('symbol', '2')))
+        (list
+          ('symbol', '1')
+          ('symbol', '2'))))
(not
('symbol', '1')))
* set:
@@ -3089,8 +3129,9 @@  issue2549 - correct optimizations
('symbol', 'last')
(list
(or
-          ('symbol', '1')
-          ('symbol', '2'))
+          (list
+            ('symbol', '1')
+            ('symbol', '2')))
('symbol', '1')))
(not
('symbol', '2')))

```